string-search - 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）。