关于KMP中预处理表格的疑惑

Question

回顾KMP算法，并对KMP中计算后缀前缀计数表的特定行感到困惑。

算法kmp_table： 输入： 字符，W（字进行分析来） 整数数组的数组，T（待填充的表） 输出： 没什么（但在操作期间，它填充表）

define variables: 
    an integer, pos ← 2 (the current position we are computing in T) 
    an integer, cnd ← 0 (the zero-based index in W of the next 
    character of the current candidate substring) 

(the first few values are fixed but different from what the algorithm 
might suggest) 
let T[0] ← -1, T[1] ← 0 

while pos is less than the length of W, do: 
    (first case: the substring continues) 
    if W[pos - 1] = W[cnd], 
     let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1 

    (second case: it doesn't, but we can fall back) 
    otherwise, if cnd > 0, let cnd ← T[cnd] 

    (third case: we have run out of candidates. Note cnd = 0) 
    otherwise, let T[pos] ← 0, pos ← pos + 1 

上面是直接从维基百科。我有点困惑，如果cnd > 0为什么设置cnd := T[cnd]，不应该被重置回0，如果我们再次开始？

Answer 1

很明显，T[0] = -1等等设置cnd到T[cnd = 0] = -1在下一次迭代中将等于读取W[cnd = -1]并且在字符串之外。至少因为这个原因，你需要特别治疗cnd > 0 vs cnd == 0。

我们比较cnd为0的真正原因是，T[cnd]应该给我们的位置在W[]到倒带时，有一个部分字符串匹配的W[cnd]左侧。但是，T[0]不能用于此目的，因为W[0]的左侧没有任何内容。

为什么设置cnd：= T [cnd]，不应该重置为0，就好像我们再次启动一样？

您错过了算法的全部要点。如果您在部分匹配后重新开始位置0，则返回初始算法。 T[]包含倒带位置，正如你可以从正下方的W[]和T[]样本表中看到的那样，并不总是0.因此，不是一直回到位置0，而是有时会转到其他位置并继续匹配从那里。这就是让算法比天真的更具可扩展性的原因。