KMP算法中求next數組的實質

在串比對模式中，kmp算法較蠻力法是高效的算法，我覺得其中最重要的一點就是求next數組：

看了很多資料才弄明白求next數組是怎麼求的，我發現我的忘性真的比記性大很多，每次看到kmp算法求next數組都得花很長時間去看怎麼求，雖然看了很多遍了，但還是容易忘，是以我今天非得把它記下來，這樣我下次看到的時候就可以直接看我的總結了，哈，可惡的記性，總是這麼不争氣。設目标串為s，需要比對串為t：

next[j]數組生成的實質：

    next[j]數組的值其實就等于串t1t2...tj-1中相同的字首子串和字尾子串的最大長度加1。再則找字首和字尾相同的最大真子串，實質上仍然是一個模式比對，隻是比對的模式串和目标串是同一個串t。是以就有：

1、next[1]=0

2、設next[j]=k

     若tk=tj時，則 next[j+1]=next[j]+1

     若tk≠tj ， 則 next[j+1]=next[k]+1

3. 若不存在比對的子串:  next[j+1]=1

例：已知比對串t=“abcaabbabcab”，則：

模式t:   a  b  c  a  a  b  b  a  b   c  a   b

next[j]:

0  1  1  1  2  2  3  1  2   3  4   5

next函數的算法：

void next(string t,int next[])

{

   int j=1,k=0;

   next[1]=0;

   while(j<t.len)

  {

      if(k=0||t.str[j]==t.str[k])

      {

 j++;k++;next[j]=k;

      }

      else

            k=next[k];

  }

}