algorithm - 如果前缀表全为零，KMP 的性能如何？

Question

如果我的模式是“Brudasca”，那么 KMP 前缀表将全部清零。在那种情况下，KMP 和平凡的解决方案之间是否有任何性能差异？这不是 O(n*m) 的最坏情况吗？

Answer 1

这是 KMP 算法的最佳情况。我们看一下KMP的失败/前缀函数（KMP-search也有类似的逻辑）：

int curLen = 0;   
for (int i = 1; i < len; ++i) { 
    while (curLen > 0 && s[curLen] != s[i]) 
        curLen = prefixFunc[curLen - 1]; 

    if (s[curLen] == s[i]) 
        ++curLen;

    prefixFunc[i] = curLen;
}

每次迭代的主要复杂性在于一个while循环。在这个循环中，算法试图找到具有最大长度的适当前缀。当我们的前缀表充满零时，这个 while 循环将最多进行一次迭代。这意味着没有适当的子前缀，我们应该从头开始。Оverall 复杂性将是线性的。

一般来说，KMP算法的复杂度是线性的，与输入数据无关。