KMP算法比简化的Boyer-Moore算法执行的比较少吗？

Question

KMP（Knuth-Morris-Pratt）算法比简化的Boyer-Moore算法执行的比较次数少吗？

Answer 1

的Boyers Moore算法通常应以较少的比较执行从here

报价应该相当清楚的是，如果是正常，一个给定的字母犯规出现在所有的搜索字符串的情况下，那么这个算法只需要大约N/M个字符比较（N =长度（s1），M =长度（s2）） - 对KMP算法有很大改进，但仍然需要N.但是，如果不是这种情况，那么我们可能需要再次进行N + M比较（使用算法的完整版本）。幸运的是，对于许多应用程序，我们接近N/M性能。如果搜索字符串非常大，那么它可能会出现一个给定的字符，但与其他算法相比，我们仍然有一个很好的改进（如果字符随机分布在一个字符串中，大约N * 2/alphabet_size）。