知识卡片
前缀函数给出下一候选位移
已匹配q字符后失配,令k=π[q],下一可能有效的位移是s′=s+(q−k)。此前k字符必然与已读文本对齐,无需重比;选最长可复用前缀对应最小安全位移,避免漏匹配。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
Given that q characters have matched successfully at shift s, the next potentially valid shift is at s′ = s + (q – π[q]) as shown in part (b). The procedure KMP-MATCHER on the following page gives the Knuth-Morris-Pratt matching algorithm. The procedure follows from FINITE-AUTOMATON-MATCHER for the most part. To compute π, KMP-MATCHER calls the auxiliary procedure COMPUTE-PREFIX-FUNCTION. These two
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[40000,45000))。
- 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。
- 原始内容:Given that q characters have matched successfully at shift s , the next potentially valid shift is at s ′ = s + ( q – π [ q ]) as shown in part (b). The procedure KMP-M ATCHER on the following page gives the Knuth-Morris-Pratt matching algorithm. The procedure follows from F INITE -A UTOMATON -M ATCHER for the most part. To compute π , KMP-M ATCHER calls the auxiliary procedure C OMPUTE -P REFIX -F UNCTION . These two