一、KMP算法步驟：

1. 用模式串（子串）求出next數(shù)組
2. 用next數(shù)組進(jìn)行字符串匹配

二、求next數(shù)組：

1. next[j]數(shù)組到底是什么呢？

• 數(shù)組的下標(biāo)代表了“已匹配前綴的下一個(gè)位置”，元素的值則是“最長(zhǎng)可匹配前綴子串的下一個(gè)位置”。
• 當(dāng)模式串中第j個(gè)字符發(fā)生不匹配時(shí)，應(yīng)從next[j]處的字符開(kāi)始于主串匹配。

2. 如何求next[j]數(shù)組（假設(shè)數(shù)組從1開(kāi)始存儲(chǔ)）？
   next[1]=0（數(shù)組從1開(kāi)始存儲(chǔ)）
   -. 手工求解法，next[j] = j 前面的子串的前部和后部重合長(zhǎng)度+1
   -. 代碼方法
3. 代碼方法求next[j]數(shù)組（假設(shè)數(shù)組從1開(kāi)始存儲(chǔ)）：
   1. 我們?cè)O(shè)置兩個(gè)變量i和j，其中i表示“已匹配前綴的下一個(gè)位置/在第i 個(gè)字符發(fā)生不匹配，也是待填充的數(shù)組下標(biāo)，j表示“最長(zhǎng)可匹配前綴子串的下一個(gè)位置”，也就是待填充的數(shù)組元素值。
      2. 具體過(guò)程見(jiàn)參考文獻(xiàn)、數(shù)據(jù)結(jié)構(gòu)書或是活頁(yè)本筆記
4. 用next數(shù)組進(jìn)行字符串匹配:

建議用數(shù)據(jù)結(jié)構(gòu)高分筆記上有答案的題練習(xí)一下

參考文獻(xiàn)

KMP算法詳解，注意本文數(shù)組從0開(kāi)始