KMP算法最坏情况分析

Question

我不明白KMP如何维护O(m+n)。我在找“aaaaaaaaaa.”中的模式"aaaab“。

• 图案: aaaab (长度n)
• 弦乐:啊……(长度m)

那么前缀表将是

aaaab 01230

每当'b‘发生不匹配时，前缀长度总是为0。所以这种模式只向右移动了一步。

啊..。 aaaab 啊..。 _aaaab 啊..。 __aaaab

对于每一次试验，我需要比较完整的n次，因为错配发生在最后的'b‘。因此，它仍然需要O(m*n)比较。

有人能解释KMP是如何为我得到O(m+n)的吗？提前谢谢。

Answer 1

诀窍是，当您遇到不匹配时，不只是将字符串中的位置提前一个字符。KMP的设计就是为了避免这样做。在你的例子中，错配发生在4个连续匹配a's之后。在这4a‘s中没有b，所以您可以将字符串中的搜索位置提高4，而不是1。您继续这样做，最后得到O(m)。

为了使所有这些都能工作，KMP使用模式预先计算了一个助手表。这个表将基本告诉您，在模式中的给定位置发生不匹配时，如何提前字符串中的位置。结果表明，该表也是以线性时间O(n)构造的。

有关示例、详细信息和(伪)代码，请参阅维基百科和其他地方。