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

Question

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

Answer 1

这是 KMP 算法的最佳情况。再看看KMP的failure/prefix函数(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 循环最多有一次迭代。这意味着没有合适的子前缀，我们应该从头开始。整个复杂度都是线性的。

一般来说，无论输入数据如何，KMP 算法的复杂度都是线性的。