KMP文字列パターンマッチングの詳細(5)

次に、2つ目の表現方法を用いたモード値のマッチング関数(
next[0]=0
)

int my_KMP(char *S, char *T, int pos) 
{ 
int i = pos, j = 0;//pos(S    0≤pos<StrLength(S)) 
while ( S[i] != '\0' && T[j] != '\0' ) 
{ 
    if (S[i] == T[j] ) 
     { 
         ++i; 
             ++j; //         
     } 
   else             // a b a b c a a b c 
                    // 0 0 0 1 2 0 1 1 2 
   {              //-1 0 -1 0 2 -1 1 0 2 
      i++; 
     j = next[j];     /*   S[i] !=T[j] ，
                       S[i] T[next[j]]     。  next[0]=0。
                 next[]  。*/ 
   } 
}//while 
if ( T[j] == '\0' ) 
    return (i-j); //     
else 
     return -1; 
} // my_KMP 

 
六.後の話
--KMP
の歴史
[
この話は書き写しだ
]
Cook
于
1970
年に証明された1つの理論は、プッシュダウンオートマトンと呼ばれるコンピュータ抽象モデルを用いて解決できるいずれの問題も、実際のコンピュータ(より正確にはランダムアクセス機を用いる)を用いて問題規模に対応する時間内に解決できることも得られる.特に、この理論は、1つのアルゴリズムが約
m+n
の時間内にパターンマッチングの問題を解決します.
m
および
n
テキストとパターン列の配列を格納する最大インデックスです.
Knuth
および
Pratt
再建に努めた
Cook
の証明により,このモードマッチングアルゴリズムが作成された.ほぼ同じ時間で、
Morris
テキストエディタを設計する実際の問題を考慮する過程で、同じアルゴリズムが作成されました.ここでは,すべてのアルゴリズムが「霊光一現」で発見されたわけではないが,理論化されたコンピュータ科学は確かに実際の応用に応用される場合がある.