algorithm - Knuth Morris Pratt 算法比较

Question

我一直在备考的时候遇到这个问题，请大家帮忙

For any alignment of pattern P and text T, suppose a mismatch occurs at P[i+1] and T[k] during the execution of KMP algorithm How many times does T[k] come into comparison in total during the execution of KMP algorithm (SPi is non-optimized)

我遇到的可能的解决方案是

1. i-SPi
2. SPi+1
3. n-i
4. n-SPi

但它们在某些情况下都失败了，

Answer 1

所有情况都没有单一的答案。

您仍然可以给出比较次数的上限，如果 P 中的所有符号都相同，就会发现它。尝试计算一下。

如果这还不够，请尝试使用此属性:KMP 将比较 T[k] 与 P[SP_i]，然后与 P[SP_{SP i+1}] 等等，直到出现以下两个选项之一:

• 给定的字母匹配 T[k]
• 给定SP的值为0

根据 P 和 T，上述两种情况可能以许多不同的方式发生，因此不可能给出一个封闭的公式。