知识卡片
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]。整个过程只重用已经确认相等的字符,与显式匹配自动机的转移一致,而不回退文本指针。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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