索引：如果我們按照普通方法求這個問題就是一一比較，然後移一位再一一比較，，，這樣的結果顯示是超時，因此前輩們總結出一種算法，它可以不需要一位一位的移，有時候可以移好多位，這樣就可以很快得出答案了。
在這個算法中我們首先要對子串a進行分析，子串一般是比較短的，我們定義一個同樣大小的數組next，分別對應子串裡的每一位，我們分析子串裡各個字符前後的重復與否，進行記錄。
分析的結果就是如果next數組裡的數不等於0，則說明子串的前綴和後綴有重復。（前綴，後綴的定義不明白的可以問問度娘）
借用一下別人的例子說明：
所以求這個next數組是第一步，也很重要，它的模板為下邊，不長，但灰常神奇，前輩們太厲害啊
void get_next(int pl) //pl為子串的長度
{ int i=0,j=-1;
while(i<pl)
{ if(j==-1||p[i]=p[j]) //p為子串
{ i++;j++;
p[i]=j; }
else
j=next[i];
}
}
而KMP就是利用這個next數組來比較的，代碼和next的模板類似，直接套著用：
int KMP(int pl,int sl) //sl為字符串長度
{ int i=0,j=0,sum=0;
get_next(pl);
while(i<sl&&j<pl) //s為字符串
{ if(j==-1||p[j]==s[i])
{ i++;j++; }
else
j=next[j];
if(j==pl)
{ sum++;j=next[j];}
}
return sum;
}
next+KMP就可以求出子串在母串中的個數了，接下來就是next數組其他應用：
1、求一個字符串中的循環串，next數組模板+以下代碼：
求出next數組後，
for(i=1;i<=pl;i++)
{len=i-next[i]; //len位循環串長度
if(len!=i&&i%len==0)
cout<<len<<" "<<pl/len<<endl; //求出循環串長度和循環次數
}
2、求一個字符串的前綴和後綴重復的長度，next數組模板+以下代碼：
求出next數組後，
int j=0;
for(int i=pl;p[i]!=-1;)
{ sum[j++]=i; //sum數組裡存放的就是前後綴重復子串的長度，然後遍歷sum數組輸出就好了
i=next[i];
}
next數組的應用，多理解理解，習題網址 ：http://acm.hust.edu.cn/vjudge/contest/121814#status
密碼nefu
