This Little Miracle-Knuth-Morris-Pratt（CLC）アルゴリズム

Knuth-Morris-Prattアルゴリズムは 、ストリング内のサブストリング（パターン）を検索するために使用されます。 それはもっと簡単かもしれないようです。線に沿って移動し、文字をパターンと順次比較します。 一致しませんでした。比較の開始点を1ステップ移動して、再度比較します。 パターンを見つけるか、行の終わりに達するまで、というように。 関数は次のようなものです。

//      //        -1,    int find(char *, char *) { // i-     // j-     for (int i=0;[i];++i) { for (int j=0;;++j) { if (![j]) return i; //   if([i+j]!=[j]) break; } //   ,    } //   return -1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

簡単な検索ケース 'needle'-サンプル 'stackistogiststigstigigstogstog needle stack stack needle stack'-検索文字列 良いのは、内側のサイクルがすぐに中断されるときです（単純な場合のように、たとえば、ステップ1〜3で）。 ただし、サンプルと文字列に頻繁にネストされた部分が繰り返し含まれている場合（上記の難しいケースのように）、内部ループはサンプルの終わり近くで中断し、検索時間はO（<サンプル長> * <ストリング長>）として評価されます。 ストリングの長さが10万で、サンプルの長さが100の場合、O（1000万）が得られます。 もちろん、100の長さのサンプルを見つけることは非常にまれですが、オリンピアードタスクでは「検索する」ことは一般的なことです。したがって、単純な検索は多くの場合適切ではありません。 、そしてその場で、あなたが単語を入力するとき（ブラウザがこれをどれほど速くするかに気づいていますか）？ KMPアルゴリズムは、文字列とその速度O（<サンプル長> + <文字列長>）内のすべてのサンプルを検出するため、大きなテキスト/サンプルまたは弱いプロセッサ（低予算の携帯電話など）では競合しません。 なぜ「小さい」のですか？ ILCのハイライトはプレフィックス関数であり、非常に小さいためです。 なぜ「奇跡」なのですか？ 完全に異なる問題を解決するように思われるため、この解決策は、素晴らしいトリックの後、文字列内のサンプルのすべての出現を見つける問題の解決策になります。プレフィックス関数が何をどのように行うかを理解するために、複雑な文字列を見てみましょう その下の行は、行内のシンボルの番号（位置）（アルゴリズムの説明の都合上、1で番号を検討してください）であり、一番下の行はプレフィックス長の配列M、プレフィックス機能を理解するためのキーです。 Kは1〜6で、プレフィックス文字列（文字列の最初のインデックスで始まる部分文字列）とサフィックス（文字列の位置7（これは「私たちの」文字a）の長さKの最後の文字を持つ部分文字列） 注：長さ4の場合、接尾辞（文字のシーケンスとして）は接頭辞と一致し、これは接尾辞が接頭辞と一致するKの最大値です。 プレフィックス長の配列の対応する位置（7）に入力されるのはそれです。 K = 7の場合、接頭辞も接尾辞と一致することに気付くでしょう。これは同じ行であるためです。 しかし、この些細なケースは私たちには適していない、なぜなら アルゴリズムを機能させるには、サブストリングが必要ですS-ソースストリングを示しますS（n）-長さnのストリングSの先頭（プレフィックス）、S [n]-ストリングSの位置nのシンボルS. M [n]配列内の値S（M [n]）-位置nの最大長の接頭辞および接尾辞と同じ行（簡潔にするため、P（n）で示します）。 文字列P（n）は一種の「仮想」であり、形成されず、どこにも書き込まれません。 これは、長さM [n]の元の文字列Sの開始フラグメント1です。 そして、この最初のfragment1は、長さM [n]のfragment2と一致し（文字のシーケンスとして）、その最後の文字は位置nにあります。 M [n] = 0の場合、一致はありません：配列の位置7は値M [7] = 4で埋められ、最長行はP（7）=長さ4の ' aaba '（自然）で、位置8に移動して埋めますM [8]。 1から7までのすべてのプレフィックスとサフィックスの長さを愚かに数え、それらを比較し、最大長を位置8に書き込むことができます。しかし、他の方法（ILCの後）に進みます。 長さkの最大の長い行P（8）を見つけましょう。これは、位置8の接頭辞と接尾辞です。最初のk-1文字からの行p7は、位置k-1の接頭辞と接尾辞です。 7番目のポジションで最も長いという事実ではありません。 ただし、p7 = P7であることが判明した場合、P8はP7の1文字の拡張です。 P7を1ポジション拡張できるかどうかを確認するには、サフィックスに追加された文字（これは文字S [8] = a ）が次のプレフィックス文字と一致するかどうかを確認する必要があります。 接頭辞aの次の文字は、位置M [7] + 1 = 5にあります（これがなぜかを考えてください）。 一致した場合（そして、この場合は一致した場合）、タスクは完了します-M [8] = M [7] +1、および8番目の位置にあるP（8）= P（7）+文字S [8] = a 。 P（8）= ' aabaa 'を取得します。 拡張が成功すると、配列の次の値を計算するために必要な比較は1つだけです。 ちなみに、配列に沿って移動する場合、値は最大1増加する可能性があります。 便宜上、複雑な行を繰り返して、上下に移動する必要がないようにします。 別のケース-P8を展開できませんでした。 文字S [9] = aは、位置M [8] + 1 = 6 bの文字列Sの文字と一致しませんでした。 サフィックスは簡単に展開されます（新しい文字が単に末尾に追加されるため）が、問題のあるプレフィックスが付いているため、 接尾辞に追加される文字は、次の接頭辞文字と一致しない場合があります。 接頭辞P（k）が収まらない場合、同じ接尾辞を持つ別の短い接頭辞を見つける必要があり、それを展開してみてください。 ただし、接頭辞は短く、同じ接尾辞ではS [M [M [k]]）です。 配列Mを埋めるとき、各要素には同じ接尾辞を持つ最長の接頭辞の長さが含まれます。 したがって、S（M [k]）を展開できなかった場合は、S（M [M [k]]）なども一致するまで、または長さがゼロになるまで（次の文字Sを単純に比較する必要があります） 1mの文字列S）。 必要なすべての情報がすでに配列Mにあるため、適切なプレフィックスの検索サイクルは非常に速く終了します。この行では、P（8）はP（7）の1文字だけの拡張であり、1回の比較が必要です。 ただし、S [9] = aおよびS [M [8] + 1 = 6] = bであるため、P（8）をP（9）に展開できませんでした。 長さM [8] = 5のプレフィックスP8が適合しなかったため、長さM [5] = 2のプレフィックスを試します。 また、S [2 + 1] = bに適合しません。 長さM [2] = 1のプレフィックスを試してみます。 S [1 + 1] = a 。 したがって、M [9] = 2、拡張可能なプレフィックスの長さより1つ多くなります。 M [10]を埋めるには、2つの比較が必要です（確認できます）。 ただし、11〜17の要素を入力するには、1つの比較が必要です。 その結果、配列値の計算にはO（文字列の長さ）のオーダーの時間がかかるため、塗りつぶしアルゴリズムを使用すると、多かれ少なかれ明確になります。

私たちはトリックに目を向けます。

文字列aabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaのサンプルabaaaを見つけるには 記号「@ 」はセパレーターの役割を果たしますが、サンプルや検索行には見当たりません（このような記号だけを選択する必要があります）。 配列の11、14、19、22の位置を見てみましょう。 配列の値は5です。これは、長さ5のサフィックス（検索文字列のフラグメント）が5つのプレフィックス文字に一致することを意味します。 プレフィックスの5文字-これが検索のパターンです！ 検索アルゴリズムは次のとおりです-セパレータを使用してサンプルと検索文字列を接着し、接頭辞関数の「接着」を渡し、サンプルの長さに等しい要素を配列で調べます。 値がセパレータ文字と値のためにサンプルの長さを超えないことがわかりますサンプルの長さと等しい値は、元の検索文字列に対応する位置にのみ表示できます。 接着された文字列の長さは<サンプル長> + <文字列長>であるため、記事の冒頭で述べたように、計算時間はO（<サンプル長> + <文字列長>）と推定されます。 必要なバッファプレフィックス関数のボリュームは<サンプル長> + <ライン長>ですが、バッファ<サンプル長>が十分になるようにプレフィックス関数を変更できます（付録の変更例）

プレフィックス機能

そして今、プレフィックス関数の例。 上記の説明との違いは、C言語の慣例に従って、インデックスは0からカウントされることです。

C ++の例

この関数は、文字列プレフィックスの長さのベクトルを返し、文字列は文字列として渡されます（長さを計算する必要はありません）

 vector<size_t> prefix_function (string s) { size_t n = s.length(); vector<size_t> pi(n); //  i-  (  i-1)           i. // p[0]=0 , p[1]=1,      for (size_t i=1; i<n; ++i) { // ,  -   size_t j = pi[i-1]; //   -,   while ((j > 0) && (s[i] != s[j])) //   , j = pi[j-1]; //    - if (s[i] == s[j]) ++j; //   ( ) - pi[i] = j; } return pi; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cの例

関数は何も返しません。 最初のパラメーターは文字列へのポインターであり、2番目はプレフィックス長の入力された配列へのポインターです。3番目のpは文字列と配列の長さです。

 //     size_t,   int void prefix_function (char *s, int *pi, size_t n) { pi[0]=0; //  i-  (  i-1)           i. // p[0]=0 , p[1]=1,      for (size_t i=1; i<n; ++i) { int j = pi[i-1]; while ((j > 0) && (s[i] != s[j])) //   j = pi[j-1]; //     (   ) if (s[i] == s[j]) //  ++j; pi[i] = j; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、議論の結果として追加されました。 パターンと検索文字列は、異なるパラメーターで渡されます。 それらを「一緒に接着する」必要はありません。 プレフィックス長の配列は、パターンに対してのみ入力されます。

 //   ,       int f(size_t i) { printf("%d\n",i); return 1; } // str  . // obr ,  . // pi      (    ). // int f(size_t i)   ,   , //       str . //   0,      1,   . void prefix_find (char *str, char *obr, size_t *pi, int (*f)(size_t)) { pi[0]=0; //  i-  (  i-1)   //          i. // p[0]=0 , p[1]=1,      size_t l; //    //       for (l=1; obr[l]; ++l) { size_t j = pi[l-1]; while ((j > 0) && (obr[l] != obr[j])) //   j = pi[j-1]; //     (   ) if (obr[l] == obr[j]) //  ++j; pi[l] = j; } size_t j=0; //   ,     //   .        i for (size_t i=0; str[i]; ++i) {
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場所は、ILCの有効性の鍵です。 文字列の次の文字とパターンが一致しなかった場合、パターンを1文字移動せず、最初から文字列と比較しません（記事の冒頭のプリミティブ検索のように）。 パターンを数文字シフトして、str [i]とobr [j]を1回比較します。 一致しない場合、文字が一致するか、パターンの先頭に到達するまで、パターンを再度シフトします。 T.O. 検索バーに沿って後方に移動するのではなく、前方に移動します（ただし停止します）。

  while ((j > 0) && (str[i] != obr[j])) //         .  , //   ,   j       //    j+1   (  j)  i+1  . j = pi[j-1]; //  j=0,         if (str[i] == obr[j]) //     ++j; //      1 if (j==l) if (!f(i-l+1)) //  ,    return; //    ,    0. } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

小さな奇跡についての私の話-ILCアルゴリズムは終わりました。 もちろん、ILCに関するこの記事は最初のものではなく、最後のものではありません。 habrahabrに関する2つの記事を次に示します。部分文字列を検索します。 Knuth – Morris –プラットアルゴリズムと部分文字列 検索と関連事項 。しかし、誰かがこの記事を自分に役立つものと考え、誰か（結局これが起こる可能性がある）がILCを適用することを願っています。 たとえ彼が作品の内部メカニズムをよく理解していなかったとしても（理解するのに遅すぎることはありません）。 KMPアルゴリズムは唯一の高速検索アルゴリズムではありませんが、（olympiadなどの問題に対して） 十分に高速であると同時にシンプルです。 Boyer-Mooreアルゴリズムは複雑さがILCに近く、特定の範囲のタスク（サンプルに反復フラグメントが含まれていない場合）の方が高速です。 しかし、その後、さまざまなタスクの範囲（記事の例のように、サンプルと検索文字列に反復シーケンスが含まれる場合）では、ILCに比べて著しく劣ります。 最後に、どちらかを選択することが好みの問題であるタスクがあります（これは議論されていません）。 場合によっては（または地域でさえ）、 Aho-KorasikアルゴリズムがILCとBoyer-Mooreの両方よりも効率的であることが判明する場合があります。 しかし、本当にこのアルゴリズムを必要とする人は、一般的な博覧会、 IMHOを必要としません。

ディスカッション補遺

O（行の長さ+サンプルの長さ）ではなくO（サンプルの長さ）を使用するように、プレフィックス関数を変更できます。 この場合、サンプルのプレフィックスの長さを保存するためだけにメモリを割り当てる必要があり、検索文字列のプレフィックスの長さは配列に保存されません。 現在の位置の長さは変数に保存され、サンプルの長さと比較されるとすぐに（つまり、サンプルが見つかると）、プレフィックス関数は見つかったフラグメントの処理関数を呼び出します。 変更されたprefix_find関数が記事に追加されました。 実際、配列にメモリを割り当てることで節約する必要はありませんでしたが、誰かがそれを必要とする可能性があることを除外しません。Mayorovpはメモリを節約する機会に注意を喚起し、 メッセージの中でプレフィックス関数のバリアントの実装へのリンクを与えましたcoutで見つかったフラグメントの位置。 コメントによれば、staticlabは変数のタイプをsize_tに変更しました（これは実際により正確です）。記事を最後まで読んだ人のために、接頭辞と接尾辞のブロックがかなり複雑な場合にどのように編成されるかを示す図を示します：