string - 当目标是找到特定字符串的所有出现时，KMP 的最坏情况复杂度是多少？

Question

我还想知道哪种算法在查找字符串在另一个字符串中的所有出现时具有最坏情况的复杂性。看起来 Boyer-Moore 算法具有线性时间复杂度。

Answer 1

KMP 算法具有线性复杂度，可用于查找字符串中某个模式的所有出现，就像 Boyer-Moore 算法¹。如果你试图在像“aaaaaaaaa”这样的字符串中找到像“aaaaaa”这样的模式，一旦你有了第一个完整的匹配，

aaaaaaaaa
aaaaaa
 aaaaaa
      ^

边界表包含的信息是模式前缀的下一个最长可能匹配(对应于模式的最宽边界)仅短一个字符(完全匹配等同于匹配结束后的不匹配)这方面的模式)。因此，模式被进一步移动了一个位置，并且由于从边界表中已知模式的所有字符可能除了最后一个匹配之外，所以下一次比较是在最后一个模式字符和对齐的文本字符之间进行的。在这种特殊情况下(在 aⁿ 中找到 a^m 的出现)，这是朴素匹配算法的最坏情况，KMP 算法只比较每个文本字符一次。

在每个步骤中，至少有一个

• 比较的文本字符的位置
• 模式第一个字符相对于文本的位置

增加，也不会减少。比较的文本字符的位置最多可以增加length(text)-1次，第一个模式字符的位置最多可以增加length(text) - length(pattern)次，所以该算法最多需要 2*length(text) - length(pattern) - 1步骤。

预处理(边界表的构建)最多需要2*length(pattern)步骤，因此整体复杂度为 O(m+n)，不再是 m + 2*n如果 m 则执行步骤是模式的长度，n文本的长度。

¹ 请注意，通常提出的 Boyer-Moore 算法对于周期性模式和文本(如 a^m 和 a^{n 如果需要所有的匹配，因为在一个完整的匹配之后，}

aaaaaaaaa
aaaaaa
 aaaaaa
      ^
  <- <-
 ^

整个模式将被重新比较。为避免这种情况，您需要记住模式前缀在完全匹配后的移位后仍然匹配多长时间，并且只比较新字符。