テキストを与えられる txt[0 . 。 。 N-1] そしてパターン ベッド[0 . 。 。 M-1] 、txt[] 内の pat[] のすべての出現を出力する関数 search(char pat[], char txt[]) を作成します。あなたは次のように仮定するかもしれません N >M 。

例:

入力： txt[] = これはテストテキストです、pat[] = テスト
出力： インデックス 10 でパターンが見つかりました

入力： txt[] = あなたの父親
パット[] = AABA
出力： インデックス 0 で見つかったパターン、インデックス 9 で見つかったパターン、インデックス 12 で見つかったパターン

本文中のパターンの到着

Naive パターン検索アルゴリズムについては、 前の投稿 。 Naive アルゴリズムの最悪の場合の複雑さは O(m(n-m+1)) です。 KMP アルゴリズムの時間計算量は、最悪の場合でも O(n+m) です。

KMP (クヌース・モリス・プラット) パターン検索:

の 単純なパターン検索アルゴリズム 多数の一致する文字の後に不一致な文字が続く場合には、うまく機能しません。

例:

1) txt[] = AAAAAAAAAAAAAAAAAA、pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC、pat[] = ABABAC (最悪のケースではありませんが、Naive にとっては悪いケースです)

KMP マッチング アルゴリズムは、パターンの縮退特性 (パターン内に同じサブパターンが複数回出現するパターン) を使用し、最悪の場合の複雑さを改善します。 O(n+m) 。

KMP のアルゴリズムの背後にある基本的な考え方は、(いくつかの一致の後) 不一致を検出するたびに、次のウィンドウのテキスト内の文字の一部がすでにわかっているということです。この情報を利用して、一致することがわかっている文字との一致を回避します。

マッチングの概要

txt = あああああああああ
パット = AAAA
の最初のウィンドウを比較します TXT と 同じ

txt = ああああ 父親
偶数 = ああああ 【初期位置】
一致するものを見つけます。これは同じです 単純な文字列マッチング 。

次のステップでは、次のウィンドウを比較します。 TXT と 同じ 。

txt = ああああ 破壊する
偶数 = ああああ 【パターンを1つずらした】

ここで、KMP は Naive に対して最適化を実行します。この 2 番目のウィンドウでは、パターンの 4 番目の A のみを比較します。
現在のウィンドウのテキストの 4 番目の文字を使用して、現在のウィンドウが一致するかどうかを判断します。私たちは知っているので
最初の 3 文字は一致しますが、最初の 3 文字の一致は省略しました。

Inkscape vs Gimp

前処理は必要ですか?

上記の説明から、スキップされる文字数をどのように知るかという重要な疑問が生じます。これを知るには、
パターンを前処理し、スキップする文字数を示す整数配列 lps[] を準備します。

前処理の概要:

• KMP アルゴリズムは、pat[] を前処理し、補助を構築します。 lps[] サイズの メートル (パターンのサイズと同じ) マッチング中に文字をスキップするために使用されます。
• 名前 lps は、サフィックスでもある最長の適切なプレフィックスを示します。適切なプレフィックスとは、文字列全体が許可されていないプレフィックスです。たとえば、ABC の接頭辞は、、A、AB、ABC です。適切なプレフィックスは、A および AB です。文字列のサフィックスは、C、BC、および ABC です。
• サブパターンで lp を検索します。より明確に、プレフィックスとサフィックスの両方であるパターンのサブ文字列に焦点を当てます。
• 各サブパターン pat[0..i] (i = 0 ～ m-1) について、lps[i] は、サブパターン pat[0..i] のサフィックスでもある、一致する適切なプレフィックスの最大長を格納します。 ]。

lps[i] = pat[0..i] の最長の適切なプレフィックスであり、pat[0..i] のサフィックスでもあります。

注記： lps[i] は、適切なサフィックスでもある最長のプレフィックスとして定義することもできます。部分文字列全体が考慮されないように、1 か所で適切に使用する必要があります。

lps[] 構築の例:

パターン AAAA の場合、lps[] は [0、1、2、3] です。

パターン ABCDE の場合、lps[] は [0, 0, 0, 0, 0] です。

パターン AABAACAABAA の場合、lps[] は [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5] です。

パターン AAACAAAAAC の場合、lps[] は [0, 1, 2, 0, 1, 2, 3, 3, 3, 4] です。

パターン AAAABAAA の場合、lps[] は [0, 1, 2, 0, 1, 2, 3] です。

前処理アルゴリズム:

前処理部分では、

• 値を計算します lps[] 。これを行うために、最長のプレフィックス サフィックス値の長さを追跡します (次を使用します)。 のみ この目的のための変数) 前のインデックス用
• 初期化する LP[0] そして のみ 0として。
• もし パット[レン] そして ベッド 一致するとインクリメントします のみ 1 ずつ増加し、増加した値を lps[i] に代入します。
• pat[i] と pat[len] が一致せず、len が 0 でない場合、len を lps[len-1] に更新します。
• 見る computeLPSArray() 詳細については以下のコードを参照してください

前処理 (または lps[] の構築) の図:

パット[] = ああああああ

=> len = 0、i = 0:

• lps[0] は常に 0 なので、i = 1 に移動します。

=> len = 0、i = 1:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に保存してi++を実行します。
• len = 1、lps[1] = 1、i = 2 に設定します。

=> len = 1、i = 2:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に保存してi++を実行します。
• len = 2、lps[2] = 2、i = 3 に設定します。

=> len = 2、i = 3:

• pat[len] と pat[i] が一致せず、len> 0 であるため、
• len = lps[len-1] = lps[1] = 1 を設定します。

=> len = 1、i = 3:

• pat[len] と pat[i] が一致せず、len> 0 であるため、
• len = lps[len-1] = lps[0] = 0

=> len = 0、i = 3:

• pat[len] と pat[i] が一致しず、len = 0 となるため、
• lps[3] = 0 および i = 4 を設定します。

=> len = 0、i = 4:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に格納してi++を実行します。
• len = 1、lps[4] = 1、i = 5 に設定します。

=> len = 1、i = 5:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に格納してi++を実行します。
• len = 2、lps[5] = 2、i = 6 に設定します。

=> len = 2、i = 6:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に格納してi++を実行します。
• len = 3、lps[6] = 3、i = 7

=> len = 3、i = 7:

• pat[len] と pat[i] が一致せず、len> 0 であるため、
• len = lps[len-1] = lps[2] = 2 を設定します。

=> len = 2、i = 7:

• pat[len]とpat[i]が一致するので、len++を実行し、
• それをlps[i]に格納してi++を実行します。
• len = 3、lps[7] = 3、i = 8

lps[] 全体を構築したので、ここで終了します。

KMP アルゴリズムの実装:

とは異なり、 単純なアルゴリズム では、パターンを 1 つずつスライドさせ、シフトごとにすべての文字を比較します。lps[] の値を使用して、次に一致する文字を決定します。目的は、とにかく一致するとわかっている文字には一致させないということです。

lps[] を使用して次の位置を決定する (またはスキップする文字数を知る) にはどうすればよいですか?

• j = 0 の pat[j] と現在のテキスト ウィンドウの文字との比較を開始します。
• 文字 txt[i] と pat[j] の一致を維持し、pat[j] と txt[i] が維持されている間、i と j をインクリメントし続けます。 マッチング 。
• 私たちが見るとき、 ミスマッチ
  • 文字 pat[0..j-1] が txt[i-j…i-1] と一致することがわかります (j は 0 から始まり、一致する場合にのみ増加することに注意してください)。
  • また、(上記の定義から) lps[j-1] は、適切なプレフィックスとサフィックスの両方である pat[0…j-1] の文字数であることもわかります。
  • 上記の 2 つの点から、これらの lps[j-1] 文字は txt[i-j…i-1] と一致することがわかっているため、これらの文字を一致させる必要はないと結論付けることができます。これを理解するために上の例を考えてみましょう。

上記のアルゴリズムを以下に示します。

txt[] = を考えてみましょう。 あああああああああああああああああああああああ 、パット[] = ああああ

上記の LPS 構築プロセスに従うと、 lps[] = {0、1、2、3}

-> i = 0、j = 0: txt[i] と pat[j] が一致、i++、j++ を実行

-> i = 1、j = 1: txt[i] と pat[j] が一致、i++、j++ を実行

-> i = 2、j = 2: txt[i] と pat[j] が一致、i++、j++ を実行

-> i = 3、j = 3: txt[i] と pat[j] が一致、i++、j++ を実行

-> i = 4、j = 4: j = M なので、印刷パターンが見つかり、j をリセットします。 j = lps[j-1] = lps[3] = 3

ここでは Naive アルゴリズムとは異なり、最初の 3 つは一致しません
このウィンドウの文字。 lps[j-1] の値 (上記の手順) により、次に一致する文字のインデックスが得られます。

-> i = 4、j = 3: txt[i] と pat[j] が一致、i++、j++ を実行

-> i = 5、j = 4: j == M なので、印刷パターンが見つかり、j をリセットします。 j = lps[j-1] = lps[3] = 3
ここでも Naive アルゴリズムとは異なり、このウィンドウの最初の 3 文字と一致しません。 lps[j-1] の値 (上記の手順) により、次に一致する文字のインデックスが得られます。

-> i = 5、j = 3: txt[i] と pat[j] が一致せず、j> 0 の場合は、j のみを変更します。 j = lps[j-1] = lps[2] = 2

会社と会社の違い

-> i = 5、j = 2: txt[i] と pat[j] が一致せず、j> 0 の場合は、j のみを変更します。 j = lps[j-1] = lps[1] = 1

-> i = 5、j = 1: txt[i] と pat[j] が一致せず、j> 0 の場合は、j のみを変更します。 j = lps[j-1] = lps[0] = 0

-> i = 5、j = 0: txt[i] と pat[j] が一致せず、j が 0 の場合は、i++ を実行します。

-> i = 6、j = 0: txt[i] と pat[j] は一致しますが、i++ と j++ は一致します

-> i = 7、j = 1: txt[i] と pat[j] は一致しますが、i++ と j++ は一致します

パターン内の文字と比較するのに十分な文字がテキスト内に存在するまでこの作業を続けます…

上記のアプローチの実装を以下に示します。

C++

>

>

ジャワ

>

>

Python3

ネットワークトポロジー

>

>

C#

>

>

JavaScript

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) {  $M = strlen($pat);  $N = strlen($txt);  // create lps[] that will hold the longest prefix suffix  // values for pattern  $lps=array_fill(0,$M,0);  // Preprocess the pattern (calculate lps[] array)  computeLPSArray($pat, $M, $lps);  $i = 0; // index for txt[]  $j = 0; // index for pat[]  while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  if ($j == $M) { printf('インデックス ' でパターンが見つかりました。($i - $j));  $j = $lps[$j - 1];  } // j が else と一致した後の不一致 if ($i<$N && $pat[$j] != $txt[$i]) {  // Do not match lps[0..lps[j-1]] characters,  // they will match anyway  if ($j != 0)  $j = $lps[$j - 1];  else  $i = $i + 1;  }  } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) {  // Length of the previous longest prefix suffix  $len = 0;  $lps[0] = 0; // lps[0] is always 0  // The loop calculates lps[i] for i = 1 to M-1  $i = 1;  while ($i <$M) {  if ($pat[$i] == $pat[$len]) {  $len++;  $lps[$i] = $len;  $i++;  }  else // (pat[i] != pat[len])  {  // This is tricky. Consider the example.  // AAACAAAA and i = 7. The idea is similar  // to search step.  if ($len != 0) {  $len = $lps[$len - 1];  // Also, note that we do not increment  // i here  }  else // if (len == 0)  {  $lps[$i] = 0;  $i++;  }  }  } } // Driver program to test above function  $txt = 'ABABDABACDABABCABAB';  $pat = 'ABABCABAB';  KMPSearch($pat, $txt);   // This code is contributed by chandan_jnu ?>>>
 
 
 
 
    
 
>
 
    
 
>
 
  出力  
 
Found pattern at index 10>
 
    時間計算量:    O(N+M) ここで、N はテキストの長さ、M は検出されるパターンの長さです。  
    補助スペース:    お(お)