当目标是查找某个字符串的所有出现时,KMP的最坏情况复杂度是多少？

Question

我还想知道哪种算法具有最差的案例复杂性,以便在另一个中查找所有出现的字符串.似乎Boyer-Moore的算法具有线性时间复杂度.

Answer 1

KMP算法具有线性复杂性,用于查找字符串中所有出现的模式,如Boyer-Moore算法¹.如果你试图在像"aaaaaaaaa"这样的字符串中找到像"aaaaaa"这样的模式,那么一旦你有了第一个完整的匹配,

aaaaaaaaa
aaaaaa
 aaaaaa
      ^

边界表包含模式前缀的下一个最长可能匹配(对应于模式的最宽边界)的信息只有一个字符短(完全匹配相当于模式结尾之后的不匹配)这方面).因此,图案被进一步移动一次,并且由于从边界表中已知图案的所有字符除了可能的最后一个匹配之外,下一个比较是在最后一个图案字符和对齐的文本字符之间.在这种特殊情况下(在^n中发现^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算法对于周期性模式具有O(m*n)的最坏情况复杂度,并且如果需要所有匹配则具有^m和^n的文本,因为在完全匹配之后,

aaaaaaaaa
aaaaaa
 aaaaaa
      ^
  <- <-
 ^

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