10

维基百科声称可以在 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;
}

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

4

3 回答 3

8

这一行： 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) 次。

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

于 2013-09-07T07:30:28.680 回答
4

这里已经有两个答案是正确的，但我经常认为一个完整的证明可以让事情变得更清楚。你说你想要一个 9 岁孩子的答案，但我认为这是不可行的（我认为很容易被愚弄认为这是真的 ，而实际上没有任何直觉知道为什么它是真的）。也许解决这个答案会有所帮助。

首先，外部循环运行n时间很清楚，因为i在循环内没有修改。循环中唯一可以运行多次的代码是块

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

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

pi[i] <= i

这是通过归纳来完成的。pi[0] <= 0因为它在初始化时设置过一次，pi并且再也没有被触及过。然后我们归纳地让0 < k < n并假设该主张成立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. 但是在循环的大约 6 次迭代之后，while我们 j = 3假设它在s[i] == s[j]so 行中增加了 1 j = 4 = pi[i]。那么在外循环的下一次迭代中，我们从j = 4... 开始，所以我们最多只能执行while4 次。

难题的最后一块是++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

为了使它真正正式，您可以建立上面描述的不变量，然后使用归纳来显示该循环运行的总次数，与最多相加。由此可见，循环运行的总次数是，这意味着整个外循环具有复杂性：whilepi[i]iwhileO(n)

O(n)     // from the rest of the outer loop excluding the while loop
+ O(n)   // from the while loop
=> O(n)
于 2013-09-07T10:19:12.573 回答
3

让我们从外部循环执行 n 次的事实开始，其中 n 是我们寻找的模式的长度。内部循环将 的值j至少减少 1，因为pi[j] < j. 循环最迟在 时终止j == -1，因此它最多可以减少 的值，j因为它之前增加了j++（外部循环）。由于j++在外循环n中执行的次数恰好是，因此内循环的总执行次数被限制为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 是所寻找的模式的长度。

于 2013-09-07T08:32:03.413 回答