知识卡片

普通读书笔记卡 · 3704.d.3

KMP命中后回退继续匹配

理解等级:中级

找到完整模式后,KMP把已匹配长度q重置为π[m],再处理下一文本字符。

这样既避免读取不存在的P[m+1],也保留模式自身可复用的最长边界,从而继续发现重叠出现。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Line 10 is necessary in KMP-MATCHER, because otherwise, line 4 might try to reference P[m + 1] after finding an occurrence of P. (The argument that q = σ(T[:i – 1]) upon the next execution of line 4 remains valid by the hint given in Exercise 32.4-8: that δ(m, a) = δ(π[m], a) or, equivalently, σ(Pa) = σ(P[:π[m]]a) for any a ∈ ∑.) The remaining argument for the correctness of the Knuth-Morris-Pratt algorithm follows from the correctness of FINITE-AUTOMATON-MATCHER,

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[55000,60000))。 - 结论依据:原文第32.4节的边界迭代引理、前缀函数证明或KMP状态转移推导。 - 原始内容:Line 10 is necessary in KMP-M ATCHER , because otherwise, line 4 might try to reference P [ m + 1] after finding an occurrence of P . (The argument that q = σ ( T [: i – 1]) upon the next execution of line 4 remains valid by the hint given in Exercise 32.4-8: that δ ( m , a ) = δ ( π [ m ], a ) or, equivalently, σ ( Pa ) = σ ( P [: π [ m ]] a ) for any a ∈ ∑.) The remaining argument for the correctness of the Knuth-Morris-Pratt algorithm follows from the correctness of F INITE -A UTOMATON -M ATCHER ,