引入：如何設(shè)計(jì)一個(gè)算法，判斷一個(gè)字符串中含有另一個(gè)字符串呢缚柳？比較容易想到的就是樸素模式匹配算法埃脏，時(shí)間復(fù)雜度是O(n*m)，但是kmp算法可以讓時(shí)間復(fù)雜度降低到O(n)秋忙。
這是如何做到的剂癌？
假設(shè)有兩個(gè)字符串為
A=ababbababa
B=ababa
不妨令A(yù)為主串，B為模式串翰绊，可以發(fā)現(xiàn)，A[5]和B[5]（不妨設(shè)下標(biāo)從1開(kāi)始）失配了旁壮，如果按照樸素模式匹配算法思想监嗜，那么下面該進(jìn)行比較的字符是A[2]和B[1]。實(shí)際上抡谐，并不需要這樣做裁奇，我們只需要將A[5]和B[3]相比較即可*，為什么麦撵？
當(dāng)?shù)趎個(gè)字符匹配失敗時(shí)刽肠，我們知道前n-1個(gè)字符一定是匹配成功的，也就意味著我們只需要研究模式串前n-1個(gè)字符就可以了免胃，而指向主串第n個(gè)字符的指針不需要回溯來(lái)和模式串比較音五，因此我們可以讓下一次比較是主串第n個(gè)字符和模式串前n-1中的一個(gè)字符來(lái)比較，那么讓模式串中的哪個(gè)字符來(lái)比較呢羔沙？這就不得不提到（前n-1個(gè)字符的）最長(zhǎng)公共前后綴和next數(shù)組了躺涝。
上面我們提到了，讓模式串中的哪個(gè)字符來(lái)比較扼雏，即是第 next[n] 個(gè)字符坚嗜，那么next數(shù)組又怎么求呢？
1.當(dāng)j=1時(shí)诗充，意味著模式串第一個(gè)字符與主串失配苍蔬，next值為0，我們規(guī)定了下標(biāo)從1開(kāi)始蝴蜓，這并不表示模式串中第0個(gè)字符與主串中的失配字符相比較碟绑，而是表示模式串第一個(gè)字符與主串失配字符的下一字符再進(jìn)行匹配。
2.當(dāng)存在長(zhǎng)度為k的公共前后綴，且 0 < k < j-1 時(shí)蜈敢，next值為k+1辜荠。
3.當(dāng)只存在長(zhǎng)度為k的公共前后綴（此時(shí)k = j-1）時(shí)，next值為1抓狭，表示模式串第一個(gè)字符與主串失配字符相比較伯病。
為什么？可在樸素模式匹配算法中觀察規(guī)律得出
next數(shù)組的進(jìn)一步優(yōu)化否过，nextval
根據(jù)上面的公式午笛，我們可以求出B的next數(shù)組為 0 1 1 2 3，這就是為什么 "只需將A[5]和B[3]相比較即可"苗桂。實(shí)際上可以進(jìn)一步優(yōu)化药磺，因?yàn)槲覀儼l(fā)現(xiàn)B[5]和B[3]對(duì)應(yīng)的字符都是a，再比較還是會(huì)失配煤伟，因此我們可以把next[5]的值改為next[3]癌佩，而next[3] = 1，我們又發(fā)現(xiàn)B[1]還是a便锨，還是會(huì)失配围辙，因此我們可以把next[5]改為next[1]，值為0放案，表示B[1]與A[6]相比較姚建。同樣的道理，用這種方法吱殉，我們遍歷一遍next數(shù)組掸冤，讓next數(shù)組優(yōu)化一下。
代碼
求next數(shù)組
上面求next方法為手算友雳，代碼求next方法參考視頻https://www.bilibili.com/video/BV16X4y137qw/
根據(jù)前面的介紹容易知道稿湿，next[1] = 0, next[2] = 1,
此時(shí)若ch[1] == ch[2]，根據(jù)next數(shù)組定義沥阱，next[3] = 2缎罢，若ch[2] == ch[3]，則next[4] = 3 ·········直到
ch[n-1] !=ch[n]考杉，則可視為s1s2···sn-1 與s2s3···sn匹配失敗策精，而s1s2···s[next[n-1]-1]與s[n-(next[n-1]-1)]····sn-1是相同的，此時(shí)再比較sn和s[next[n-1]]崇棠，若相等咽袜，則next[n+1] = next[n-1]+1，否則枕稀，再按匹配失敗走询刹，若是最壞的情況一直失敗谜嫉，j會(huì)等于0，最后next[n+1] = 1凹联。
void GetNext(String T ,next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
求nextval數(shù)組
