为什么可以在O(n)时间内计算KMP故障函数？

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;
}

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

Answer 1

这一行:if(s [i] == s [j])++ j; 最多执行O(n)次.它导致p [i]值的增加.注意,p [i]以与p [i-1]相同的值开始.

现在这一行:j = pi [j-1]; 导致p [i]减少至少一个.而且由于它最多增加了O(n)次(我们的数量也会增加和减少以前的值),因此不能减少超过O(n)次.所以它也最多执行O(n)次.

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