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

Question

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

Answer 1

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

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