ひとつの比較的に通俗的なKMPのアルゴリズムは説明します

KMPアルゴリズムは文字列マッチングを処理するために用いられる.言い換えれば、2つの文字列をあげると、B列がA列のサブ列であるかどうか(A列にB列が含まれているかどうか)に答える必要があります.例えば、文字列A=「I'm matrix 67」、文字列B=「matrix」は、BがAのサブストリングであると言います.あなたは婉曲にあなたのMMに闻くことができます:“もしあなたが好きな人に告白するならば、私の名前はあなたの告白の言叶の中の子串ですか?”このような問題を解決するには、通常、我々の方法は、A列のどの位置からBとマッチングを開始し、マッチングするかどうかを検証することである.A列長がn,B列長がmの場合,この方法の複雑さはO(mn)である.多くの場合、複雑度がmnに達しない(検証時に最初の1、2文字だけを見ても不一致が発見される)が、A=「aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa最悪の場合のO(n)のアルゴリズム(ここではm<=nと仮定する)、すなわち伝説のKMPアルゴリズムを紹介する.KMPというのは、このアルゴリズムがKnuth、Morris、Prattの3つから提案され、この3人の名前の最初のアルファベットを取ったからです.このとき、AVLツリーがなぜAVLなのか、Bellman-Fordがなぜ鉄棒なのかが急に分かったのかもしれません.時々7、8人が研究したことがありますが、どうやって命名しますか?通常、これは「3 x+1問題」などの論争を避けるために、人の名前で命名する必要はありません.話が遠くなった.個人的にはKMPは最も言う必要のないものだと思います.これはネット上で多くの資料を見つけることができるからです.しかし、ネット上の言い方は基本的に「移動(shift)」や「Next関数」などの概念に関連しており、誤解を生みやすい(少なくとも1年半前にこれらの資料を見てKMPを勉強したときは分からなかった).ここでは、KMPアルゴリズムを説明する方法を変えます.もし,A="abababaabacb",B="ababacb"であれば,KMPがどのように動作しているかを見てみよう.A[i-j+1..i]はB[1..j]と完全に等しいことを2つのポインタiとjでそれぞれ表した.すなわち、iは増加し続け、iの増加に応じてjが変化し、jがA[i]で終わる長さjを満たす文字列がB列の前j文字(jはもちろん大きいほど良い)にちょうど一致し、A[i+1]とB[j+1]の関係を検証する必要がある.A[i+1]=B[j+1]の場合、iとjはそれぞれ1つずつ加算される.いつj=mになったら、BはAのサブストリング(Bストリングは完了)であり、このときのi値からマッチング位置を算出することができる.A[i+1]<>B[j+1]の場合、KMPのポリシーは、A[i-j+1..i]がB[1..j]と一致し、新しいB[j+1]がA[i+1]と一致するようにjの位置を調整することである(したがって、iおよびjが増加し続けることができる).i=j=5の場合を見てみましょう.i=1 2 3 4 5 6 7 8 9…A=a b a b a b a b…B=a b a b a c b j=1 2 3 4 5 6 7このとき、A[6]<>B[6].これは,このときjが5に等しくないことを示しており,jをそれより小さい値j′に変更する.j'はいくらかもしれませんか.よく考えてみると、j'はB[1..j]の頭j'文字と末尾j'文字を完全に等しくしなければならない(jがj'になってからiとjの性質を維持し続けることができる).このj'はもちろん大きいほどいいです.ここでは,B[1.5]=「ababa」で,頭3文字と末尾3文字が「aba」である.一方,新しいjが3の場合,A[6]はちょうどB[4]と等しい.すると、iは6になり、jは4になる:i=1 2 3 4 5 6 8…A=a b a b a b a b a b a b…B=a b a b a c b j=1 2 3 4 5 6 7以上の例から、新しいjはiに関係なく、B列のみに関係することができることがわかる.このような配列P[j]を完全に前処理することができ,B配列のj番目のアルファベットにマッチングし,j+1番目のアルファベットがマッチングできない場合,新しいjが最大でどれだけ大きいかを示す.P[j]はすべてB[1..P[j]=B[j-P[j]+1を満たすべきである.j]の最大値.その後、A[7]=B[5]、iとjはそれぞれ1ずつ増加した.このとき、A[i+1]<>B[j+1]の場合、i=1 2 3 4 5 6 8…A=a b a b a b a b a b a b…B=a b a b a c b j=1 2 3 4 6 7 P[5]=3のため、従って、新しいj=3:i=1 2 3 4 5 6 7 9…A=a b a b a b a b a b…B=a b a b a c b j=1 2 3 4 5 6 7の場合、新しいj=3はA[i+1]=B[j+1]を満たすことができず、このとき再びj値を小さくし、jを再びP[3]:i=1 2 3 4 5 6 7 8 9・・A=a b a b a b a b a b a b・・B=a b a b a c b j=1 2 3 4 5 6 7と更新したが、現在、iはまだ7、jは1となっている.このときA[8]はB[j+1]に等しくない.このように、jはP[1]に減少しなければならない.すなわち、0:i=1 2 3 4 5 6 8 9......A=a b a b a b a b a b a b a b...B=a b a b a c b j=0 1 2 3 4 5 6 7ついに、A[8]=B[1]、iは8になり、jは1になる.実際、jが0になってもA[i+1]=B[j+1](例えばA[8]=「d」を満たすことができない場合がある.したがって,正確には,j=0になったとき,i値を増やしたが,A[i]=B[1]が現れるまでjを無視した.このプロセスのコードは短い(本当に短い)ので、  j:=0;
  for i:=1 to n do
  begin
     while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
     if B[j+1]=A[i] then j:=j+1;
     if j=m then
     begin
        writeln('Pattern occurs with shift ',i-m);
        j:=P[j];
     end;
  end;の最後のj:=P[j]は、プログラムを継続させるために与えられています.私たちは複数のマッチングを見つけることができるからです.このプログラムは想像以上に簡単かもしれません.i値の増加に対して、コードはforループを使用しているからです.したがって、このコードは、文字列Aをスキャンし、Bのどの位置に一致するかを更新することをイメージ的に理解することができる.今、私たちはまた2つの重要な問題を残しました:1、どうしてこのプログラムは線形ですか;二、P配列をどのように迅速に前処理するか.なぜこのプログラムはO(n)なのですか?実際、主な論争はwhileサイクルが実行回数に不確定な要素を生じさせたことにある.時間的複雑さの償却解析における主な戦略を用い,簡単に言えば,ある変数や関数値の変化を観察することによって,ばらばらで乱雑で不規則な実行回数を積算する.KMPの時間的複雑度分析は,償却分析の典型といえる.上記のプログラムのj値から着手する.whileサイクルを実行するたびにjは減少するが(負には減少できない)、j値を変更する場所は5行目のみである.この行が実行されるたびに、jは1しか加算できません.従って,全過程においてjは最大n個の1を加えた.したがって、jは最大n回の減少の機会しかない(j値の減少の回数は当然nを超えてはならない.jは永遠に非負の整数であるからである).これはwhileサイクルが合計で最大n回実行されたことを示している.償却分析によれば,各forサイクルに均等に広げた後,1回のforサイクルの複雑度はO(1)であった.全過程は明らかにO(n)であった.このような解析は,後のP配列の前処理過程においても同様に有効であり,同様に前処理過程の複雑さO(m)を得ることができる.前処理はPの定義に従ってO(m^2)乃至O(m^3)と書く必要はない.P[1],P[2],...,P［j−1］の値を用いてP［j］の値を得た.先ほどのB=「ababacb」について、P[1],P[2],P[3]およびP[4]を求めた場合、P[5]およびP[6]をどのように求めるべきかを見てみましょう.P[4]=2であれば、P[5]は明らかにP[4]+1に等しい.P[4]から分かるように、B[1,2]はすでにB[3,4]と等しくなっており、現在はB[3]=B[5]もあるので、P[5]はP[4]の後に1文字を加えて得ることができる.P[6]もP[5]+1に等しいか.明らかにそうではない.なぜなら、B[P[5]+1]<>B[6].では、「一歩下がる」ことを考えましょう.P[6]がP[5]の場合に含まれるサブストリングから得られる可能性があるか,すなわちP[6]=P[5]+1であるかを考える.ここで納得できない場合は、1 2 3 4 5 6 7 B=a b a b a c b P=0 0 1 2 3?P[5]=3は、B[1..3]とB[3..5]が共に「aba」であるためである.P[3]=1は,B[1],B[3],B[5]ともに「a」であることを示している.P[6]がP[5]から得られない以上、P[3]から得られるかもしれない(B[2]がちょうどB[6]と等しい場合、P[6]はP[3]+1に等しい).明らかに、P[6]は、B[2]<>B[6]のため、P[3]によっても得られない.実際、このままP[1]まで押してもだめで、最後に、私たちは、P[6]=0を得ました.どうしてこの前処理過程は前のKMPメインプログラムとこんなに似ているのですか?実は、KMPの前処理自体がB列の「自己整合」の過程である.そのコードは上のコードと似ています:  P[1]:=0;
  j:=0;
  for i:=2 to m do
  begin
     while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
     if B[j+1]=B[i] then j:=j+1;
     P[i]:=j;
  end;最後に補足します:KMPアルゴリズムはB列しか前処理していないので、このアルゴリズムはこのような問題に適しています:1つのB列と1つの異なるA列を与えて、BにどのA列のサブ列なのかを聞きます.