KMP模式匹配算法的时间复杂度可以是O(m*n)？

Question

我在这里几乎没有看到什么答案，但仍然需要一些澄清。KMP具有O(n+m)最坏的时间复杂度。但我所理解的是，在最坏的情况下，应该是O(n*m)。让我们举一个例子：

string(n):  aaaaaaaaa
pattern(m): aaab

前3个字符匹配。然后是错配。"aaa"的适当前缀后缀表将返回2，因此只能根据KMP进行(3-2)=1的字符移动。因此，我们比较n*(m-1)的时间，然后我们可以得出结论，在这种情况下没有匹配。有效的时间复杂度是O(n*m)。

有人能解释一下在这种情况下O(m+n)是怎么回事吗？除了适当的前缀后缀表之外，我还需要考虑其他任何事情吗?并将其视为特例。KMP中提到过吗？对这种特殊情况进行详细解释将是非常有帮助的。

Answer 1

因此，只有(3-2)=1字符移动可以根据KMP。

是。

因此，我们比较n*(m-1)的次数，才能得出在这种情况下没有匹配的结论。

不是的。接下来我们比较的是a (文本的第四部分)和a (模式的第三部分)，它给出2+1=3作为当前匹配的长度。

让我们使用T=aaaaaaaaa文本和P=aaab模式示例。

• 在位置1，我们有T1=P1，所以匹配的长度是1。
• 在位置2，我们有T2=P2，所以匹配的长度是2。
• 在第3位，我们有T3=P3，所以比赛的长度是3。
• 在第4位，我们有T4≠P4。匹配的长度减少到pref(3)=2 (负步长)。
• 在第4位，我们又有了T4=P3，所以比赛的长度是3。
• 在5号位置，我们有T5≠P4。匹配的长度减少到pref(3)=2 (负步长)。
• 在第5位，我们有T5=P3，所以比赛的长度是3。
• 诸若此类。

正如你所看到的，从位置4开始，对于每个位置，我们做了两个步骤，而不是一个。但我们并不是在任何时候比较子串，而只是比较单个字符。位置的数目是{x}}，负步骤的数目最多是{#T}}，所以步骤的总数相对于x~T_x是线性的。