algorithm - KMP的LPS计算时间复杂度

Question

虽然到处都提到我们在计算 KMP 的 LPS 时只回溯内循环中增加的数量，但不清楚为什么整体复杂度为 O(length(pat))。

Answer 1

KMP 维护两个索引：

k - 因为您有匹配的模式 i - 当前匹配的 Text 中的最新符号。

第一部分非常简单，您只需将符号与您的文本进行比较，如果它可以增加 i

如果他们不这样做，我们使用预先计算的前缀函数来缩短当前匹配的模式，并尝试在较短的版本上再次匹配相同的 x。以此类推，直到我们有一个匹配和++i，或者直到k达到i并且我们有一个全新的开始。

最坏的情况是，您将拥有 k 并且 i 完全通过 Text 提供 2 * len(T) 步骤。

所以复杂度一直是 O(T + P)。在实际查找匹配项时，我们不依赖前缀的长度。这意味着，如果您使用一种模式的多个匹配项进行 KMP，您仍然会得到 O(T + P)

Answer 2

看来我想通了。代码如下所示：

while (j < len1) {
        if (needle[i] == needle[j]) {
            tab[j] = i+1;
            j++;
            i++;
        }
        else {
            if (i == 0) {
                tab[j] = 0;
                j++;
            }
            else
                i = tab[i-1];
        }
    }

所以基本上我们从不递减 j，在某些迭代中（else->else）我们不递增 j，并且 i 向后移动直到我们达到 0。这种向后移动可以只要 j 移动。因此，如果 j 移动了 n 步，我们不能在最多 n 次迭代中增加 j。这使得总迭代次数为 n+n=2n 因此复杂度为 O(n)。