いつKMPアルゴリズムを使うのが良いですか？

Question

私は、KMPアルゴリズムがヘルパー配列に依存することは、接尾辞に似た接頭辞があることを理解しています。 ヘルパー配列にすべてのゼロが含まれているため、上記の条件が満たされていないと効率的ではありません。 ランタイムはO（m + n）になりますか？ 私が正しいとすれば、この場合、より良い部分文字列アルゴリズムは何ですか？

Answer 1

KMPがいつ使用するのが良いかを理解するには、「何が代案なのですか？」という質問をするのが役に立ちます。

KMPには、最悪の場合効率が保証されているという利点があります。前処理時間は常にO（n）であり、探索時間は常にO（m）である。最悪の場合の入力はありません。不幸になる確率はありません。非常に長い文字列（大きなn）を本当に大きな文字列（大きいm）の中で検索している場合、これは他のアルゴリズム（病理学的入力にはΘ（mn）の時間がかかります）、またはBoyer-Moore（最悪の場合はΘ（mn）になることがあります。文字列の重複部分が多くない場合はKMPが必要ではないかもしれませんが、悪いケースがあるかどうか心配する必要はありません。

KMPには、処理が1回で済むという素晴らしい特性もあります。あなたが同じ部分文字列のロットとたくさんの時間を検索することを知っているなら、O（n）前処理作業を一度実行してから、長さがmの文字列を検索することができます。 （m）。