KMP算法最坏情况分析
KMP algorithm worst case analysis
我无法理解 KMP 是如何保持 O(m+n) 的。我正在寻找“aaaaaaaaaa...”中的模式“aaaab”。
- 模式：aaaab（长度 n）
- 字符串：aaaaaaaaaa...（长度 m）
那么前缀[=30=]就是
aaaab
01230
每次 'b' 上发生不匹配时，其前缀长度始终为 0。因此模式仅向右移动一步。
aaaaaaaaaa...
aaaab
aaaaaaaaaa...
_aaaab
aaaaaaaaaa...
__aaaab
并且对于每次试验，我都需要比较完整的 n 次，因为不匹配发生在最后 'b'。因此它仍然需要 O(m*n) 次比较。
谁能给我解释一下 KMP 是如何得到 O(m+n) 的？提前致谢。
诀窍在于，当您遇到不匹配时，您不只是将字符串中的位置提前 1 个字符。 KMP 旨在避免这样做。在您的示例中，不匹配发生在 4 个连续匹配 a 之后。这 4 个 a 中没有 b，因此您可以将字符串中的搜索位置提高 4，而不是 1。您继续这样做，最终得到 O(m)。
为了使所有这些都起作用，KMP 使用该模式来预先计算一个助手 table。 table 基本上会告诉您在模式中的给定位置发生不匹配时，字符串中的位置要前进多少。原来table也是线性时间建立的，O(n).
有关示例、详细信息和（伪）代码，请参阅维基百科和其他地方。
我无法理解 KMP 是如何保持 O(m+n) 的。我正在寻找“aaaaaaaaaa...”中的模式“aaaab”。
- 模式：aaaab（长度 n）
- 字符串：aaaaaaaaaa...（长度 m）
那么前缀[=30=]就是
aaaab
01230
每次 'b' 上发生不匹配时，其前缀长度始终为 0。因此模式仅向右移动一步。
aaaaaaaaaa...
aaaab
aaaaaaaaaa...
_aaaab
aaaaaaaaaa...
__aaaab
并且对于每次试验，我都需要比较完整的 n 次，因为不匹配发生在最后 'b'。因此它仍然需要 O(m*n) 次比较。
谁能给我解释一下 KMP 是如何得到 O(m+n) 的？提前致谢。
诀窍在于，当您遇到不匹配时，您不只是将字符串中的位置提前 1 个字符。 KMP 旨在避免这样做。在您的示例中，不匹配发生在 4 个连续匹配 a 之后。这 4 个 a 中没有 b，因此您可以将字符串中的搜索位置提高 4，而不是 1。您继续这样做，最终得到 O(m)。
为了使所有这些都起作用，KMP 使用该模式来预先计算一个助手 table。 table 基本上会告诉您在模式中的给定位置发生不匹配时，字符串中的位置要前进多少。原来table也是线性时间建立的，O(n).
有关示例、详细信息和（伪）代码，请参阅维基百科和其他地方。