1

为什么 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--)  {
    }
}

并且将所有可能的 ij 组合也称为状态将需要一个m 数组，因此运行时不会是 O(n m)。

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

4

1 回答 1

0

其实，现在想想。它是 O(n+m)。只是将其可视化为两个窗口移动。

于 2019-06-20T09:46:37.627 回答