知识卡片
KMP命中后回退继续匹配
找到完整模式后,KMP把已匹配长度q重置为π[m],再处理下一文本字符。
这样既避免读取不存在的P[m+1],也保留模式自身可复用的最长边界,从而继续发现重叠出现。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 ,