一、KMP算法步骤:
- 用模式串(子串)求出next数组
- 用next数组进行字符串匹配
二、求next数组:
- next[j]数组到底是什么呢?
- 数组的下标代表了“已匹配前缀的下一个位置”,元素的值则是“最长可匹配前缀子串的下一个位置”。
- 当模式串中第j个字符发生不匹配时,应从next[j]处的字符开始于主串匹配。
- 如何求next[j]数组(假设数组从1开始存储)?
next[1]=0(数组从1开始存储)
-. 手工求解法,next[j] = j 前面的子串的前部和后部重合长度+1
-. 代码方法 - 代码方法求next[j]数组(假设数组从1开始存储):
- 我们设置两个变量i和j,其中i表示“已匹配前缀的下一个位置/在第i 个字符发生不匹配,也是待填充的数组下标,j表示“最长可匹配前缀子串的下一个位置”,也就是待填充的数组元素值。
2. 具体过程见参考文献、数据结构书或是活页本笔记
- 我们设置两个变量i和j,其中i表示“已匹配前缀的下一个位置/在第i 个字符发生不匹配,也是待填充的数组下标,j表示“最长可匹配前缀子串的下一个位置”,也就是待填充的数组元素值。
- 用next数组进行字符串匹配: