KMPアルゴリズムのベストケースシナリオでの比較の最小数はいくつですか？
2786 次
2 に答える
4
最良のケースは、探している文字列がテキスト文字列の先頭にある場合に発生します。この場合、k文字列内の文字列を探しているn場合、比較の最良の数はkです。
また、文字の単語に基づいてテーブルを計算するオーバーヘッドを考慮する必要がありますk。これにより、一致する文字が見つからない場合にスキップする文字を知ることができます。いずれにせよ、この構築はで行われO(k)ます。
于 2012-10-20T21:55:23.920 に答える
1
最良の場合の比較の最小数は文字列の長さです。つまり、最初に一致するものが見つかりました。アルゴリズムはO（n）です。これは、上限または最悪のシナリオでn回の比較が行われることを意味します。ここで、nは検索する文字列の長さです。ウィキはかなり良いです。 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
于 2012-10-20T21:56:22.260 に答える