はじめに
KMPアルゴリズムは、2つの文字列SとPがある場合の文字列マッチング問題を解くために使われます。通常、Sをテキスト文字列、Pをパターン文字列と呼びます。 
暴力的なマッチング
この問題を解く最も簡単な方法は、パターン文字列Pの先頭をテキスト文字列Sの各添え字に順番に揃え、SとPの後続文字が正確に等しいかどうかを判定することです。 
暴力的なマッチングのコードは、特定のマッチングプロセスを観察するコードに従って、次のとおりです。
int match(string s,string p){
int n=s.length();
int m=p.length();
int i=0,j=0;
while(i<n && j<m){
if(s[i]==p[j]) { ++i;++j; }
else { i=i-j+1;j=0; }//現在の文字がマッチしない場合、pを1ビット右にシフトする。
}
return j<m?-1:i-j;//マッチングに失敗すると-1が返される。
}
i=0,j=0とし、まずS[0]とP[0]を比較し、両者が等しくないことを確認してから、i=i-j+1,j=0とします。
i=1,j=0とし、P[1]とP[0]を比較して等しいと判断したら、i+=1,j+=1とし、i=2,j=1とします。
i=2、j=1。この時点でS[2]とP[0]が比較され、等しいことがわかります。
i=i-j+1、j=0、ならi=2、これは文字列Pを右に1つずらしたのと同じです。
その後の処理も同様で、列挙されることはなく、最終的にi=4でマッチが成功します。
暴力的なマッチング・アルゴリズムの欠点は、ミスマッチがパターン文字列Pを1ビットだけ右にシフトさせることができるという事実にあります。 上記のマッチングプロセスの最初のステップでは、この時点でi = 6、j = 5は、S[i]とP[j]の不一致は、i = i - j +1=2、j = 0になることがわかり、その後、S[2]とP[0]を比較するために行く、実際には、冗長な計算、それはS[2]とP[0]が等しくないという状況のマッチングから推測することができるので、つまり、Pはまだ不一致になることを確認した後、1位後ろにシフトされ、理由は次のとおりです。理由は以下の通りです：
ステップ1では、S[1]=P[0]、S[2]=P[1]、P[0]とP[1]が等しくないことが既に分かっており、この3つの情報からS[2]とP[0]も等しくないことが分かるので、ミスマッチの後にPを1ビットだけ後ろにシフトする必要はなく、直接2ビット後ろにシフトしてから後続のマッチングに進めばよいのです。
そして、パターン文字列Pの特徴に応じて、暴力的なマッチングのプロセスを最適化し、不一致の場合にパターン文字列Pをできるだけ後方に移動させる必要があります。
KMP
KMP アルゴリズムは、パターン文字列 P のすべての接頭辞文字列のうち、同じ接頭辞と接尾辞の最大長をカウントするために、次の配列を作成します。
接頭辞と接尾辞
パターン文字列P=ABCABDを例にとると、Pの接頭辞はA、AB、ABC、ABCA、ABCAB、ABCABの5つ。 Pの接尾辞はD、BD、ABD、CABD、BCABDの5つ。
つまり、プレフィックスは元の文字列の最初の文字を含む任意の部分文字列、サフィックスは元の文字列の最後の文字を含む任意の部分文字列とすることができますが、プレフィックスもサフィックスも元の文字列そのものとすることはできません。
next配列の意味
ここでは次配列の意味を説明し、次配列を解く具体的な手順は3.4で説明します。 パターン文字列Pの次配列を以下に示します。
next[i]は、部分文字列P[0~i-1]の同じ接頭辞と接尾辞の最大長を意味し、コードを書きやすくするためにnext[0]=-1という特別な規定があります。
next[1]は、P[0]='A'、next[1]=0 の場合の最大同一接頭辞接尾辞長を表します。
next[2]は、P[0~1]='AB'の最大同一接頭辞接尾辞長を表します。
next[3]は、P[0~2]='ABC'の最大同一接頭辞接尾辞長を表します。
next[4]は、P[0~3]='ABCA'に対して、同一の接頭辞と接尾辞の最大長を表します。
next[5]は、P[0~4]='ABCAB'の接頭辞と接尾辞の長さの最大値を表します。
KMPアルゴリズムの流れ
KMPアルゴリズムを使用したマッチングのコードは以下のとおりで、ブルート・フォース・マッチングに非常に似ています。 現在のテキスト文字列Sが添え字iにマッチし、パターン文字列Pが添え字jにマッチすると仮定すると、j=-1またはS[i]=P[j]の場合、後続の文字のマッチングを続行します。 そうでなければ、不一致の場合、直接 j=next[j] とし、i は変更せず、この操作はパターン文字列 P を 1 ビットだけ後退させるのではなく、j-next[j] ビットを移動させます。
int match(string s,string p){
int n=s.length();
int m=p.length();
int i=0,j=0;
while(i<n && j<m){
if(j==-1 || s[i]==p[j]) { ++i;++j }
else j=nxt[j];
}
return j<m?-1:i-j;//マッチングに失敗すると-1が返される。
}
例題のまま、コードに従って正確なマッチング・プロセスをご覧ください。
i=0,j=0,まずS[0]とP[0]を比較して等しくないことを確認し、j=next[0]=-1とします。
この時点では、j=-1, ++i, ++jであり、その後i=1, j=0となるので、これはPが右に1つシフトしていることに相当します。
j=next[5]=2のように、i=6, j=5で不一致が発生するまで、後続の文字を順番にマッチさせます。
この時点でi=6、j=2となり、Pは4ビットを直接右に移動したことになります！
マッチメイク。
next配列を解く
つまり、next[i]を計算した後、next[0]、next[1]、...、next[i-1]を計算します。next[i-1]が導出され、そこから次のようにnext[i]の値を計算することができます。
これは、P[0~i-1] の公開プレフィックス-サフィックス長の最大値です。
この時点で、P[0~i-2]の最大公開接頭辞接尾辞長であるnext[i-1]をすでに知っているので、もしP[next[i-1]]=P[i-1]ならば、next[i]=next[i-1]+1となり、+1が上乗せされることになり、次の図がより直感的になります。
もしP[next[i-1]]！= P[i-1]の場合、解を続けるにはどうすればよいでしょうか？k=next[i-1]とし、next[k]の値、つまりnext[next[i-1]]の値まで行き、P[next[k]]=P[i-1]とわかれば、next[i]=next[k]+1とすれば、次の図のように直感的になります。
もし P[next[k]]！= P[i-1]となり、どう解くかというと、next[next[k]]の値を見続ける、つまりnext[next[next[i-1]]]の値を見て、対応する文字の位置とP[i-1]が等しいかを比較して行きます。 こうしてどんどん進み、等しい文字が見つからなければnext[i]=0。
次の配列を解くコードです。
int nxt[maxn];
void getnext(string p){
int m=p.length();
nxt[0]=-1;
int i=0,k=-1;
while(i+1<m){//次の[i+1]次の配列の値は，毎回，次の配列の前に計算される．，k=next[i]
if(k==-1 || p[i]==p[k]){
++i;
++k;
nxt[i]=k;
}
else k=nxt[k];
}
}
要約すると
int nxt[maxn];
void getnext(string p){
int m=p.length();
nxt[0]=-1;
int i=0,k=-1;
while(i+1<m){//次の[i+1]次の配列の値は，毎回，次の配列の前に計算される．，k=next[i]
if(k==-1 || p[i]==p[k]){
++i;
++k;
nxt[i]=k;
}
else k=nxt[k];
}
}
int match(string s,string p){
int n=s.length();
int m=p.length();
int i=0,j=0;
while(i<n && j<m){
if(j==-1 || s[i]==p[j]) { ++i;++j }
else j=nxt[j];
}
return j<m?-1:i-j;//マッチングに失敗すると-1が返される。
}
