Knuth Morris Pratt (KMP) algorithm

Knuth, Morris, Pratt によって考案された KMP アルゴリズムは、T[n], P[m] に対して最悪の場合でも n + m 回の比較で文字列照合を行うことができます（O(n + m)）。

Brute force アルゴリズムでは、不一致 T[i] ≠ P[j] が検出されると、i = i - j + 1 として i のポインタをリセットしていました。KMP アルゴリズムは、不一致 T[i] ≠ P[j] を検出した時点で、テキストとパタンがどこまで一致しているかが分かっていることを有効に利用します。つまり不一致 T[i] ≠ P[j] を検出した時点で 1 ≦ k ≦ j について T[i - k] = P[j - k] ということが既に分かっているのです（下図参照）。

具体的な例をいくつか見てみましょう。

Case 1:

右図の例において、不一致 T[i] ≠ P[j] が検出された時点で、T[i - j] = b, T[i - j + 1] = a, ... T[i - 1] = a ということが既に分かっています。
つまり、P[0] = b ということから ( T[1] = T[2] = T[3] ) ≠ P[0] ということが既に分かっているので、Brute force のように i のポインタを i - j + 1 に後戻りさせるのは明らかに無駄な処理を発生させます。
この例の場合、i はそのまま、j = 0 としてパタンのチェックを再開することができます。

Case 2:

右図の例において、不一致 T[i] ≠ P[j] が検出された時点で、T[0] = T[2] = a, T[1] = T[3] = b ということが既に分かっています。
P[0] ≠ P[1] = T[1] ということが既に分かっているので、Brute force のように i のポインタを i - j + 1 に後戻りさせるのは無駄になります。
では、テキトウに i を１つだけ後戻りさせてみましょう（i = i - 1）。しかしこれは、P[0] = T[2], P[1] = T[3] という事実、つまりパタンを見逃してしまいます。これは、少なくとも i を１つしか後戻りさせなかったら、パタンを見逃してしまうことを意味します。
この例の場合、i を２つ後戻りさせ（i = i - 2）、チェックを再開することが正しいのです。

KMP アルゴリズムでは、この「P[j] の位置で不一致が検出された時、i をどこまで後戻りさせるか」をテーブル N として記録しておき有効利用します。N の値は P にのみ依存することから、N は照合の処理をする前にあらかじめ計算しておくことができます。

j > 0 に対する N[j] の値は、k < j かつ パタンの先頭から j 文字の部分列において、最初の k 文字と最後の k 文字が一致するような最大の k です。

このパタンをあるテキストと照合してみましょう。

P[8] で不一致が検出されたとすると、k = N[8] = 5 なので、i を 5 つ後戻りさせ照合を再開すればよいことになります。

しかし、上で述べたように、 1 ≦ k ≦ j について T[i - k] = P[j - k] ということが既に分かっているので、元の i の位置から再開することができます。従って、N[j] は「i をどこまで後戻りさせるか」と表現するよりは「j をどこから再開するか」と表現した方が直感的に分かりやすいと思います。

ただし、P[0] で不一致が検出された場合は、無条件に i = i + 1, j = 0 となります。この例外処理を行うために、以下のプログラムのように N[0] = -1 としておくと便利です。

void initNext( string P, int m, int N[]){
    int i, j;
    N[0] = -1;
    for ( i = 0, j = -1; i < m; i++, j++, N[i] = j )
    while( ( j >= 0 ) && ( P[i] != P[j] ) ) j = N[j];
}

int KMPSearch( string T, int n, string P, int m ){
    int N[MAX];
    initNext( P, m, N );
    
    int i, j;
    i = j = 0;
    while ( i < n ){
        while( i < n && j < m ){
            while ( j >= 0 && T[i] != P[j] ) j = N[j];
            i++; j++;
        }
        if ( j == m ) {
            print( i - j );
            j = N[j];
        }
    }
}

上記のプログラムは、若干巧妙なので、P[0] で不一致が検出されたときの処理を明示的に書いたプログラム例を以下に示します。

void initNext( string P, int m, int N[]){
    int i, j;
    N[0] = -1;
    for ( i = 0, j = -1; i < m; i++, j++, N[i] = j )
    while( ( j >= 0 ) && ( P[i] != P[j] ) ) j = N[j];
}

int KMPSearch( string T, int n, string P, int m ){
    int N[MAX];
    initNext( P, m, N );
    
    int i, j;
    i = j = 0;
    
    while ( i < n ){
        while( i < n && j < m ){
            if ( j == 0 ){
                if ( T[i] != P[j] ){ j = 0; i++; }
                else { i++; j++; }
            } else {
                if ( T[i] != P[j] ){ j = N[j]; }
                else { i++; j++; }
            }
        }
        if ( j == m ) {
            printf("P appers at %d\n", i - j); j = N[j];
        }
    }
}