string-search - KMP 算法执行的比较次数是否比简化的 Boyer-Moore 算法少？

Question

KMP (Knuth-Morris-Pratt) 算法执行的比较次数是否比简化的 Boyer-Moore 算法少？

Answer 1

Boyers Moore 算法通常应该以较少的比较来执行，引用自 here

It should be reasonably clear that, if it is normally the case that a given letter doesnt appear at all in the search string, then this algorithm only requires approx N/M character comparisons (N=length(s1), M=length(s2)) - a big improvement on the KMP algorithm, which still requires N. However, if this is not the case then we may need up to N+M comparisons again (with the full version of the algorithm). Fortunately, for many applications we get close to the N/M performance. If the search string is very large, then it is likely that a given character WILL appear in it, but we still get a good improvement compared with the other algorithms (approx N*2/alphabet_size if characters are randomly distributed in a string).