algorithm - Knuth Morris Pratt 算法比较

Question

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

对于模式 P 和文本 T 的任意对齐，假设在 KMP 算法执行过程中 P[i+1] 和 T[k] 发生不匹配 KMP 执行过程中，T[k] 总共比较了多少次算法（SPi 未优化）

我遇到的可能解决方案是

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

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

Answer 1

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

您仍然可以给出比较次数的上限，如果所有符号P都相同，则可以找到它。试着计算一下。

如果这还不够，请尝试使用此属性：KMP 将T[k]与 P[SP _i ] 进行比较，然后与 P[SP _{SP i +1} ] 进行比较，依此类推，直到出现以下两个选项之一：

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

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