また、別の文字列のすべての出現を見つけるために、どのアルゴリズムが最悪の場合の複雑さを持っているかを知りたいです。Boyer–Moore のアルゴリズムには線形時間の複雑さがあるようです。
25524 次
4 に答える
4
KMPに関する長い記事がhttp://en.wikipedia.org/wiki/Knuth-morris-prattにあります。
アルゴリズムの2つの部分は、それぞれO（k）とO（n）の複雑さを持っているため、アルゴリズム全体の複雑さはO（n + k）です。
これらの複雑さは、WまたはSに繰り返しパターンがいくつあっても同じです。（引用符の終わり）
したがって、KMP検索の総コストは、文字列とパターンの文字数に比例します。文字列内でパターンが複数出現する必要がある場合でも、これは当てはまると思います。そうでない場合は、patternQを検索することを検討してください。ここで、Qはテキストに出現しない文字であり、KMPの状態が表示される場所を書き留めます。 Qまでのすべてに一致していること。
于 2012-02-07T19:52:02.917 に答える
3
で文字列の Pi 関数を数えることができますO(length)。KMP は length を持つ特別な文字列を作成しn+m+1、その上で Pi 関数をカウントするため、いずれにしても複雑さはO(n+m+1)=O(n+m)
于 2012-02-07T19:39:11.663 に答える