string-search - KMP アルゴリズムは単純化された Boyer-Moore アルゴリズムよりも少ない比較を実行しますか?

Question

KMP (Knuth–Morris–Pratt) アルゴリズムは単純化された Boyer-Moore アルゴリズムよりも少ない比較を実行しますか?

Answer 1

Boyers Moore アルゴリズムは通常、ここから引用するより少ない比較で実行する必要があります。

通常、特定の文字が検索文字列にまったく表示されない場合、このアルゴリズムはおよそ N/M 文字の比較 (N=length(s1), M=length(s2) のみを必要とすることは明らかです。 )) - まだ N を必要とする KMP アルゴリズムの大幅な改善。ただし、そうでない場合は、最大で N+M の比較が必要になる場合があります (アルゴリズムのフル バージョンを使用)。幸いなことに、多くのアプリケーションで N/M 性能に近づきます。検索文字列が非常に大きい場合、特定の文字がその中に表示される可能性がありますが、他のアルゴリズムと比較して優れた改善が得られます (文字が文字列内にランダムに分布している場合、約 N*2/alphabet_size)。