← 返回刚才阅读的位置

知识卡片

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

KMP失配沿边界链模拟转移

理解等级:高级

以下按1起始下标记P[1]…P[m];P[:q]表示前q个字符。KMP的状态q表示已读文本的最长后缀恰好等于P[:q]。π[q]是P[:q]的最长真边界长度,沿q、π[q]、π[π[q]]……回退,就按从长到短枚举所有仍可能对齐的边界。

当q、遇到新字符a而P[q+1]≠a时,KMP沿这条边界链回退,找到首个满足P[q′+1]=a的q′,再进入状态q′+1;若连空边界q′=0也不能接,就进入0。若q=m,算法已经报告一次完整匹配,要先令q←π[m],再处理下一个字符,因而不会访问不存在的P[m+1]。整个过程只重用已经确认相等的字符,与显式匹配自动机的转移一致,而不回退文本指针。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Thus, the intuition is that KMP-MATCHER iterates through the states in π*[q] in decreasing order, stopping at some state q′ and then possibly moving to state q′+1. Although that might seem like a lot of work just to simulate computing δ(q, a), bear in mind that asymptotically, KMP-MATCHER is no slower than FINITE-AUTOMATON-MATCHER. We are now ready to formally prove the correctness of the Knuth-Morris-Pratt algorithm. By Theorem 32.4, we have that q = σ(T[:i]) after each time line 3 of FINITE-AUTOMATON-MATCHER executes. Therefore, it suffices to show that the same

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[55000,60000))。 - 结论依据:原文第32.4节的边界迭代引理、前缀函数证明或KMP状态转移推导。 - 原始内容:Thus, the intuition is that KMP-M ATCHER iterates through the states in π *[ q ] in decreasing order, stopping at some state q ′ and then possibly moving to state q ′+1. Although that might seem like a lot of work just to simulate computing δ ( q , a ), bear in mind that asymptotically, KMP-M ATCHER is no slower than F INITE -A UTOMATON -M ATCHER . We are now ready to formally prove the correctness of the Knuth-Morris-Pratt algorithm. By Theorem 32.4, we have that q = σ ( T [: i ]) after each time line 3 of F INITE -A UTOMATON -M ATCHER executes. Therefore, it suffices to show that the same