特定の文字列のすべての出現を見つけることが目的の場合、KMPの最悪の複雑さは何ですか？

Question

私はまた、どのアルゴリズムが最悪の複雑さを持っているか知りたいと思います。 Boyer-Mooreのアルゴリズムのように線形時間の複雑さがあるようです。

Answer 1

KMPアルゴリズムは、Boyer-Mooreアルゴリズム1のように、文字列内のパターンのすべての出現を見つけるための線形複雑さがあります。あなたは「aaaaaaaaa」のような文字列で「AAAAAA」のようなパターンを発見しようとした場合、あなたが最初の完全な一致を持っていたら、

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^

境界テーブルは、次の可能な最長マッチが（に対応する情報が含まれていますパターンの接頭辞の最も広い境界）は1文字だけです（完全一致は、この点でパターンの最後を過ぎた不一致に相当します）。したがって、パターンは1つの場所にさらに移動され、境界テーブルからパターンのすべての文字がおそらく最後の一致を除いて認識されるので、次の比較は最後のパターン文字と整列されたテキスト文字との間で行われる。ナイーブマッチングアルゴリズムの最悪の場合であるこの特定の場合（^mの出現をⁿとする）、KMPアルゴリズムは各テキスト文字を正確に1回比較する。少なくとも一つ

テキスト文字の位置が
• テキスト

増加に対するパターンの最初の文字の位置を比較

の各ステップにおいて

、どちらも減少しません。比較されるテキスト文字の位置は、最大でlength(text)-1倍に増加することができ、最初のパターン文字の位置は最大でlength(text) - length(pattern)倍に増加することができるので、アルゴリズムは最大で2*length(text) - length(pattern) - 1ステップを要します。

前処理（境界テーブルの構成）が最も2*length(pattern)ステップで、このように全体的な複雑さはO（M + N）であり、mは、パターンの長さとnの長さであればそれ以上m + 2*nステップが実行されない取りテキスト

はボイヤー - ムーアアルゴリズムは一般的に提示するので、^メートルおよびすべての一致が必要な場合^Nような周期パターンとテキストのためのO（M×n個）の最悪の場合の複雑性を有することに留意されたい¹完全一致後、

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^
    <- <- 
^ 

パターン全体が再比較されます。これを避けるには、完全一致後のシフト後にパターンの接頭辞がどれだけ長く一致し、新しい文字のみを比較するかを覚えておく必要があります。

Answer 2

文字列のPi関数をO(length)に数えることができます。 KMPは、長さn+m+1を持っている特別な文字列を構築し、その上にパイの機能をカウントし、どのような場合には複雑さがO(n+m+1)=O(n+m)

Answer 3

二つの部分以来

を言って終わるhttp://en.wikipedia.org/wiki/Knuth-morris-prattでKMPで長い記事がありますされますので、アルゴリズムの複雑さはそれぞれO（k）とO（n）の複雑さを持ち、アルゴリズム全体の複雑さはO（n + k）です。

これらの複雑さは関係なく、繰り返しパターンがWまたはS （終了引用符）にあるどのように多く、同じではない

だから、KMP検索の総コストは、文字列とパターンの文字の数で直線的です。文字列にパターンが複数出現する必要があっても、これが成り立つと思います。そうでない場合は、patternQを検索することを検討してください。ここでQはテキストには現れない文字で、KMPの状態を示しますQまですべて一致していることを確認してください。