algorithm - KMP算法最坏情况分析

Question

我无法理解 KMP 如何保持 O(m+n)。我正在“aaaaaaaaaa ...”中寻找模式“aaaab”。

• 模式：aaaab（长度 n）
• 字符串：aaaaaaaaaa...（长度 m）

那么前缀表将是

aaaab

01230

每次在“b”上发生不匹配时，它的前缀长度始终为 0。所以模式只向右移动了一步。

啊啊啊啊……

aaaab

啊啊啊啊……

_aaaab

啊啊啊啊……

__aaaab

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

谁能解释一下 KMP 是如何为我得到 O(m+n) 的？提前致谢。

Answer 1

诀窍是当您遇到不匹配时，您不只是将字符串中的位置提前 1 个字符。KMP 旨在避免这样做。在您的示例中，不匹配发生在 4 个连续匹配 a 之后。这 4 个 a 中没有 b，因此您可以将字符串中的搜索位置提前 4，而不是 1。您继续这样做并最终得到 O(m)。

为了使所有这些工作，KMP 使用该模式来预先计算一个帮助表。该表将基本上告诉您在模式中给定位置发生不匹配时，将字符串中的位置提前多少。事实证明，该表也是以线性时间 O(n) 构建的。

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