为什么KMP算法的失配函数可以在O(n)时间内计算？

Question

维基百科声称，失配函数表可以在O（n）时间内计算出来。

让我们看看它的“规范”实现（用C++实现）：

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

即使有内部 while 循环，为什么它能在 O(n) 时间内工作？我对算法分析并不是很擅长，所以能否有人解释一下呢？

- vortexxx192

---

你的算法有误 - 向量 pi 没有被初始化！ - Ed Heal

@EdHeal：实际上是这样的。vector<int>会将其值初始化为零。 - usamec

@usamec：还是错的，因为pi [0]通常为-1（对于第一个字符不匹配时，您不会回溯，而只会继续到下一个字符）。 - Michael Foukarakis

Answer 1

这行代码：if (s[i] == s[j]) ++j; 最多只会执行O(n)次。

它导致了p[i]的值增加。注意，p[i]的初始值与p[i-1]相同。

现在这行代码：j = pi[j-1]; 至少使得p[i]减少1。由于它最多只能执行O(n)次（我们还要计算先前数值的增加和减少），因此它不能再被减少超过O(n)次。

因此，整个时间复杂度为O(n)。

- usamec

---

它无法做到。就像我说的，循环中的条件只能满足O(n)次总计。因此，它总共执行了O(n)次。有时候，比起简单地将O(n)乘以O(n)，做一些更聪明的事情会更好。 - usamec

Answer 2

这里已经有两个正确的答案了，但我认为详细阐述一下可能会更加清晰。你说你想要一个9岁孩子可以理解的答案，但我觉得这不太现实（我认为没有直观的理解很容易被误导）。也许通过阅读这个回答，能够帮助你更好地理解。

首先，外部循环明显执行n次，因为在循环内部未修改i。唯一可能多次运行的代码是块中的代码。

while (j > 0 && s[i] != s[j])
{   
    j = pi[j-1]
}   

那么它可以运行多少次？请注意，每当满足该条件时，我们都会减少j的值，此时j最多为pi[i-1]。如果它达到0，则while循环结束。为了看清这一点的重要性，我们首先证明一个引理（你是一个非常聪明的9岁孩子）：

pi[i] <= i

这是通过归纳完成的。由于在初始化pi时设置了pi[0] <= 0并且从未再次触及，因此第一步成立。然后根据归纳法，我们假设对于0 <= a < k，命题成立。考虑p[k]的值。它恰好在pi[i] = j的行中设置一次。那么j最大可以是多少呢？通过归纳，它初始化为pi[k-1] <= k-1。在while块中，它可能会被更新为pi[j-1] <= j-1 < pi[k-1]。通过另一种小型归纳，您可以看到j永远不会超过pi[k-1]。因此，在while循环之后，我们仍然有j <= k-1。最后，它可能会增加一次，这样我们就有j <= k，所以pi[k] = j <= k（这是我们需要证明的内容）。

现在回到原点，我们问“我们可以将j的值减少多少次”？有了引理，我们现在可以看到每次while循环的迭代都会单调地减少j的值。特别是我们有：

pi[j-1] <= j-1 < j 

那么这个循环能运行多少次呢？最多是 pi[i-1] 次。敏锐的读者可能会想"你什么都没证明啊！我们知道 pi[i-1] <= i-1 但它在 while 循环内，所以它还是 O(n^2)！" 更聪明的读者注意到了这个额外的事实：

无论我们运行 j = pi[j-1] 多少次，我们都会减少 pi[i] 的值，并缩短下一次循环的迭代！

例如，假设 j = pi[i-1] = 10。但是在 while 循环的 ~6 次迭代之后，我们有 j = 3，并且假设它在 s[i] == s[j] 行中增加了 1，因此 j = 4 = pi[i]。那么在外部循环的下一次迭代中，我们从 j = 4 开始...因此我们最多只能执行 while 4 次。

谜题的最后一块是 ++j 每次循环最多运行一次。因此，我们不能在 pi 向量中有这样的东西：

0 1 2 3 4 5 1 6 1 7 1 8 1 9 1
           ^   ^   ^   ^   ^
Those spots might mean multiple iterations of the while loop if this 
could happen

为了让这个过程更加正式，您可以先建立上述不变量，然后使用归纳法来证明while循环运行的总次数加上pi[i]的次数最多为i。由此可知，while循环运行的总次数为O(n)，这意味着整个外部循环的复杂度为：

O(n)     // from the rest of the outer loop excluding the while loop
+ O(n)   // from the while loop
=> O(n) 

- rliu

Answer 3

让我们从一个事实开始，外部循环执行n次，其中n是我们寻找的模式的长度。内部循环将j的值至少减少1，因为pi[j] < j。当j == -1时，循环最迟终止，因此它最多可以将j的值减少与之前通过j++（外部循环）增加的次数相同。由于j++在外部循环中恰好执行n次，因此内部while循环的总执行次数限制为n。因此，预处理算法需要O(n)步骤。

如果您在意，可以考虑这个预处理阶段的更简单的实现：

/* ff stands for 'failure function': */
void kmp_table(const char *needle, int *ff, size_t nff)
{
    int pos = 2, cnd = 0;

    if (nff > 1){
        ff[0] = -1;
        ff[1] = 0;
    } else {
        ff[0] = -1;
    }

    while (pos < nff) {
        if (needle[pos - 1] == needle[cnd]) {
            ff[pos++] = ++cnd;
        } else if (cnd > 0) {
            cnd = ff[cnd]; /* This is O(1) for the reasons above. */
        } else {
            ff[pos++] = 0;
        }
    }
}

很明显，失败函数的时间复杂度是O(n)，其中n是所寻找的模式的长度。

- Michael Foukarakis