如果前缀表全为零，KMP的性能如何？ [英] What is the performance of KMP if the prefix table is all zero?

问题描述

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

If my pattern is "Brudasca", then the KMP prefix table will be all zeroed out. In that case, is there any performance difference between KMP and the trivial solution? And would not this be worst case of O(n*m)?

推荐答案

KMP算法。让我们看一下KMP的故障/前缀功能（KMP搜索具有类似的逻辑）：

This is the best case for KMP algorithm. Let's look at the failure/prefix function of KMP (KMP-search has similar logics):

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循环最多将进行一次迭代。这意味着没有适当的子前缀，我们应该从头开始。完全复杂是线性的。

The main complexity of each iteration is in a while-loop. In this loop, the algorithm tries to find proper prefix with maximal length. When our prefix table is full of zeroes, then this while-loop will have at most one iteration. It means that there is no proper sub-prefix and we should start from the beginning. Оverall complexity will be linear.

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

Generally speaking, the complexity of KMP algorithm is linear regardless of input data.

这篇关于如果前缀表全为零，KMP的性能如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！