algorithm - (with example) 为什么 KMP 字符串匹配 O(n)。不应该是 O(n*m) 吗？

Question

为什么 KMP 是 O(n + m)？

我知道这个问题可能已经在这里被问了一百万次，但我还没有找到一个让我信服/我理解的解决方案或一个与我的例子相匹配的问题。

/**
 * KMP algorithm of pattern matching.
 */
public boolean KMP(char []text, char []pattern){

    int lps[] = computeTemporaryArray(pattern);
    int i=0;
    int j=0;
    while(i < text.length && j < pattern.length){
        if(text[i] == pattern[j]){
            i++;
            j++;
        }else{
            if(j!=0){
                j = lps[j-1];
            }else{
                i++;
            }
        }
    }
    if(j == pattern.length){
        return true;
    }
    return false;
}

n = 文本大小
m = 图案的大小

我知道为什么它是 + m，这就是创建 lsp 数组以进行查找所需的运行时间。我不确定为什么我上面传递的代码是 O(n)。

我看到上面的“i”总是向前推进，除非它不匹配并且 j!= 0。在那种情况下，我们可以在 i 不向前移动的地方进行 while 循环的迭代，所以它不完全是O(n)

如果 lps 数组像 [1,2,3,4,5,6,0] 一样递增。如果我们未能在索引 6 处匹配，j 将更新为 5，然后 4，然后 3.... 等等，我们有效地进行了 m 次额外迭代(假设所有不匹配)。这可能发生在每一步。

看起来像

for (int i = 0; i < n; i++) {
    for (int j = i; j >=0; j--)  {
    }
}

并放置所有可能的 i j 组合，也就是状态需要一个 nm 数组，所以运行时间不会是 O(nm)。

那么是我的代码阅读错误，还是for循环的运行时分析错误，还是我的例子是不可能的？

Answer 1

其实，现在想想。它是 O(n+m)。只是把它想象成两个窗口在移动。