如果前缀table全为0，KMP的性能如何？
What is the performance of KMP if the prefix table is all zero?
如果我的模式是"Brudasca"，那么KMP前缀table将全部清零。在那种情况下，KMP 和普通解决方案之间是否存在任何性能差异？
这不是 O(n*m) 的最坏情况吗？
这是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 循环。在这个循环中，算法试图找到具有最大长度的适当前缀。当我们的前缀 table 全是零时，这个 while 循环最多有一次迭代。这意味着没有合适的子前缀，我们应该从头开始。整个复杂度都是线性的。
一般来说，无论输入数据如何，KMP算法的复杂度都是线性的。
如果我的模式是"Brudasca"，那么KMP前缀table将全部清零。在那种情况下，KMP 和普通解决方案之间是否存在任何性能差异？ 这不是 O(n*m) 的最坏情况吗？
这是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 循环。在这个循环中，算法试图找到具有最大长度的适当前缀。当我们的前缀 table 全是零时，这个 while 循环最多有一次迭代。这意味着没有合适的子前缀，我们应该从头开始。整个复杂度都是线性的。
一般来说，无论输入数据如何，KMP算法的复杂度都是线性的。