知识卡片

普通读书笔记卡 · 3706.b.1.b

自动机扫描每字符只转移一次

理解等级:中级

模式匹配自动机预先备好转移函数后,扫描文本时每读一个字符只查一次转移并检查是否进入接受态。

若转移查找为常数时间,匹配阶段是Θ(n);预处理建表时间须另外计算。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      From the simple loop structure of FINITE-AUTOMATON-MATCHER, you can see that its matching time on a text string of length n is Θ(n), assuming that each lookup of the transition function δ takes constant time. This matching time, however, does not include the preprocessing time required to compute the transition function. We address this problem later, after first proving that the procedure FINITE-AUTOMATON-MATCHER operates

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[30000,35000))。 - 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。 - 原始内容:From the simple loop structure of F INITE -A UTOMATON -M ATCHER , you can see that its matching time on a text string of length n is Θ( n ), assuming that each lookup of the transition function δ takes constant time. This matching time, however, does not include the preprocessing time required to compute the transition function. We address this problem later, after first proving that the procedure F INITE -A UTOMATON -M ATCHER operates