KMP算法-时间复杂度

Question

求kmp算法预处理部分的时间复杂度

我在学习关于KMP的知识。但是我不能理解这个algorithm.Can的时间复杂度，有人能解释一下吗？

Answer 1

我们试图计算函数的值，通常称为PI。

首先，让我们定义我们的PI函数。让S是我们的字符串。PI(i) =x <=> x是S的子串的最长后缀的长度，从S的第一个字符开始，到S的第i个字符结束，第i个字符也是S的前缀。

示例：

S: AAABACD

PI: 0120100

设S( i )是S的长度为i的前缀。

假设我们已经有了所有的值PI( 1)，PI(2)，...，PI(i -1)。计算PI(i)的时间复杂度为O(n)。我们尝试扩展S(i - 1)的最长前缀和后缀。如果这是可能的，我们就这样做，所以PI(i) = PI(i - 1) + 1。否则，我们尝试最长的前缀和后缀中的最长的前缀和后缀(尽管这听起来可能很奇怪)，依此类推。很明显，我们试图扩展的新子字符串的长度至少比前一个少了1。当我们到达长度为0的子串时，则PI(i) = 0。这就是为什么这一步的复杂度是O(n)。

因为我们计算所有1个<= i <= n的PI(i)，复杂度是O(n^2)...还是真的是这样？

让我们来讨论一下摊销的复杂性。由于每次我们尝试另一个前缀和后缀时，我们将检查的子串的长度减少至少1，因此我们肯定会在不超过PI(i - 1) -1步后停止我们的算法。设x是我们为所有1 <= j <= i- 1尝试另一个前缀和后缀的次数。然后PI(i - 1) <= i-2-x。(如果x=0，则对于所有1 <= j <= i-1，PI(j) = PI(j - 1) +1。在进行了x次额外的尝试之后，我们已经将某些j的PI(j)的值减少了至少x。)我们可以看到x< n，所以在我们的算法中总共增加了O(n)个步骤。这就是为什么摊销复杂度等于O(n)的原因。

Answer 2

KMP的时间复杂度为O(n)。KMP有一个内循环和一个外循环。最长匹配前缀变量i被初始化为0，并且在外部循环中以1的步长递增，最多为文本串长度的n倍。内部循环迭代地减少i，但它在0处停止。因此，内部循环只能在外部循环之前将其递增时才能减少i，这最多可以发生n次。

您可以将i的值视为一个资源，该资源由外部循环以步长1生成，并由内部循环以步长⩾1消耗，直到耗尽为止。