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