KMP算法

一、KMP算法步骤：

1. 用模式串（子串）求出next数组
2. 用next数组进行字符串匹配

二、求next数组：

1. next[j]数组到底是什么呢？

• 数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”。
• 当模式串中第j个字符发生不匹配时，应从next[j]处的字符开始于主串匹配。

2. 如何求next[j]数组（假设数组从1开始存储）？
   next[1]=0（数组从1开始存储）
   -. 手工求解法，next[j] = j 前面的子串的前部和后部重合长度+1
   -. 代码方法
3. 代码方法求next[j]数组（假设数组从1开始存储）：
   1. 我们设置两个变量i和j，其中i表示“已匹配前缀的下一个位置/在第i 个字符发生不匹配，也是待填充的数组下标，j表示“最长可匹配前缀子串的下一个位置”，也就是待填充的数组元素值。
      2. 具体过程见参考文献、数据结构书或是活页本笔记
4. 用next数组进行字符串匹配:

建议用数据结构高分笔记上有答案的题练习一下

参考文献

KMP算法详解，注意本文数组从0开始