What is the performance of KMP if the prefix table

问题:

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)?

回答1:

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;
}

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.

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