見ればわかる、KMPアルゴリズム乱弾～～

http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
http://www.ics.uci.edu/~eppstein/161/960227.html
Tは主列abaaabaaabaaであり、大きさは18である.pはモード列abaaであり、大きさは6である.
一般的な文字列マッチングアルゴリズムのコアコードを見てみましょう.

    for (i=0; T[i] != '\0'; i++)
    {
         for (j=0; T[i+j] != '\0' && P[j] != '\0' && T[i+j]==P[j]; j++)
                ; //      。
             if (P[j] == '\0')
               {
                     report(i);//        
               }
    }

外循環主列インデックスiは毎回++で、計18回、最後まで加算される.各ループパターン列のインデックスjの変化範囲は不定である.最悪は6回++演算です.アルゴリズムの最悪のケース18*6
KMPアルゴリズム:
まずいくつかの概念を見てみましょう.
接頭辞列:
A prefix of x is a substring u with  u  =  x0 ... xb-1   where  b   {0, ..., k} i.e. x starts with u.
接尾辞:
A suffix of x is a substring u with u  =  xk-b ... xk-1   where  b   {0, ..., k} i.e. x ends with u.
真接頭辞列と真接尾辞列:
A prefix u of x or a suffix u of x is called a proper prefix or suffix, respectively, if u x, i.e. if its length b is less than k.
境界列:
A border of x is a substring r with  r  =  x0 ... xb-1  and  r  =  xk-b ... xk-1   where  b   {0, ..., k-1} 
境界列の定義は、境界列と呼ばれる文字列を真接頭辞列と真接尾辞列を同時に満たす必要があることに注意してください!!通俗点では,境界列は両端が等しい前後の接尾辞の合体である.

rもsも境界列!
境界列の拡張:
Let x be a string and a   A a symbol. A border r of x can be extended by a, if ra is a border of xa.
下図ではr境界列がra境界列に拡張されている.

次のコードでは、
配列b[]は、我々が求めたモード列の各要素のborder値であり、境界列の長さである.
では、最初から話しましょう.あの日、ゴッドナおじいさんは、普通の文字列マッチングアルゴリズムの効率が悪いと文句を言って、彼を改善したいと思っていました.どうやって彼を改善しますか.
本質的には,通常の文字列マッチングアルゴリズムで内外がループした回数を減らすことであり,境界列を用いた.
次のコードでは、外層ループインデックスが++で18回も表示されます.
変化するのは内層の循環回数で、どのように減少するかは自分で理解しましょう!border値を使っているということですね.border値はネット上のnext値です!
では、このborder値はどうやって求めますか?次の段にジャンプしてください.

void kmpSearch()
{
    int i=0, j=0;//i     ，j      
    for ( ;i < 18; )//  ，              :-)
    {
        for ( ; j>=0 && T[i]!=p[j]; ) 
          j=b[j];  //          
          i++; j++;
        if (j==m)
        {
            report(i-j);//    ，i-j               。
            j=b[j];
        }
    }
}

 KMP算的核心组件：预处理 算法 
   
  
把下面这句看懂了，border 你就懂了。
 
  
The preprocessing algorithm comprises a loop with a variable j assuming these values. A border of width j can be extended by pi, ifpj = pi. If not, the next-widest border is examined by setting j = b[j]. The loop terminates at the latest if no border can be extended (j = -1).
 
  
 
   
  
void kmpPreprocess() //          border 。
{
    int i=0, j=-1;//i       ，j       i         border 。
    b[i]=j; //b[]      
    while (i=0 && p[i]!=p[j]) j=b[j]; //          ，              。
        i++; j++;
        b[i]=j;
    }
}