KMPアルゴリズムは単純化されたBoyer-Mooreアルゴリズムと比較してパフォーマンスが低下しますか？

Question

KMP（Knuth-Morris-Pratt）アルゴリズムは単純化されたBoyer-Mooreアルゴリズムよりも比較演算が少ないですか？

Answer 1

Boyersムーアアルゴリズムは通常、それが合理的に明確にする必要がありhere

から引用して以下の比較を行うべきである、それは通常、与えられた文字のdoesntのは全く検索文字列に表示される場合であれば、このアルゴリズムはN/M個の文字比較（N =長さ（s1）、M =長さ（s2））しか必要としません.Nを必要とするKMPアルゴリズムの大きな改良です。しかし、 （アルゴリズムのフルバージョンで）N + Mまでの比較が必要になることがあります。幸いにも、多くのアプリケーションでN/Mの性能に近づきます。検索文字列が非常に大きい場合は、指定された文字が表示される可能性がありますが、他のアルゴリズム（文字が文字列内にランダムに配置されている場合は約N * 2/alphabet_size）