我不明白KMP如何维护O（m+n）我在找“aaaaaaaa…”中的模式“aaaab”。
图案：aaaab（长度n）
字符串：aaaaaaaa…（长度m）
那么前缀表将是
aaaab公司
01230年
每次在“b”上发生不匹配时，它的前缀长度总是0所以模式只向右移动了一步。
啊啊啊啊…
aaaab公司
啊啊啊啊…
_aaaab公司
啊啊啊啊…
__aaaab公司
每次试验，我都需要比较n次，因为失配发生在最后一个“b”。因此，它仍然需要o（m*n）比较。
有谁能给我解释一下国民党是怎么得到O（M+N）的吗？提前谢谢。
最佳答案
诀窍在于，当遇到不匹配时，不只是将字符串中的位置提前1个字符KMP的目的就是避免这样做。在您的示例中，不匹配发生在连续4个匹配a之后。这4个a中没有b，因此您可以将字符串中的搜索位置提前4，而不是1。你一直这样做，结果是O（M）。
为了使所有这些工作正常进行，KMP使用模式来预计算一个helper表这个表基本上会告诉您在模式中的给定位置发生不匹配时，字符串中的位置要提前多少。结果表明，该表也是在线性时间O（n）中构建的。
有关示例、详细信息和（伪）代码，请参见维基百科和其他地方。