![[LeetCode字符串#05]基于个人理解的KMP算法图解,以及应用到strStr()函数实现](/static/background/162.jpg "[LeetCode字符串#05]基于个人理解的KMP算法图解,以及应用到strStr()函数实现")
KMP算法（用于实现 strStr(）
KMP算法
KMP算法基础理论
文本串 aabaabaaf
模式串 aabaaf
我们希望在文本串中匹配出模式串
Intro
暴力法
下面来看看KMP是怎么做的
KMP
跳转到 b 处继续匹配
因为KMP算法中使用到了 前缀表
前缀表
"当出现不匹配的值跳转到b处继续匹配"
当出现不匹配值 f 时，f 的前面的子串是 aabaa，该子串的后缀是 aa
aabaa 前缀与后缀相同的位置
b 所在之处，因此从这里开始继续匹配
最长相等前后缀是多少"
什么是前/后缀？
举个例子
aabaaf
|___|
即：
a
aa
aab
aaba
aabaa
如上面，前缀是包含首字母，不包含尾字母的所有子串
aabaaf
|___|
即：
f
af
aaf
baaf
abaaf
而后缀是只包含尾字母，不包含首字母的所有子串
如何求最长相等前后缀？
aabaaf
a 0(理论上a没有前后缀，所以为0
aa 1(前缀a,后缀a,因此是1
aab 0(a、b不等，为0
aaba 1
aabaa 2
aabaaf 0
前缀表在哪？
这里得到了一个序列（从上到下）：[0, 1, 0, 1, 2, 0]
前缀表
使用前缀表
aabaaf
010120
那么如何使用前缀表进行匹配？
的后面（b处）继续往后匹配。
子串aabaa（不匹配值前面的子串）它的最长相等前后缀的长度就是我们要继续匹配的位置
012345
aabaaf
010120
↑
也就是b的位置（即，前缀的后面）
next数组，如何去求，后面再说
KMP算法实现
next数组，因此我们需要构建它
构造next数组
构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：
- 初始化
- 处理前后缀不相同的情况
- 处理前后缀相同的情况
初始化
前缀末尾位置（不匹配值的前一个位置），i 指向后缀末尾位置。
从判断前后缀是否相同的角度解释
从初始化的角度解释
int j = -1;
next[0] = j;
其实 j 也不一定初始化为 - 1
这里是为了让next数组中的元素统一为：0，-1，1，才将 j 初始化为 -1 的
之前最长相等的前后缀长度（详见上面的解释，其实就是 j ）
之前最长相等的前后缀长度
规定好指针的定义后，现在要开始遍历判断前后缀的情况了
判断前后缀是否相同（j初始化为-1）
前后缀相等
此时 s[j+1] = s[i]，前后缀相等。
i]（注意是i）
//如果找到匹配值，j++(也就是把j+1往后移，并保存匹配值的位置(j值到next数组
if (s[i] == s[j + 1] { // 找到相同的前后缀
j++;
}
next[i] = j;
要明确一点： next数组（前缀表的具体实现）用来寻找前后缀相等时 j （指向前缀末尾位置）的位置，其存放的是
图示角度解释
前缀的定义是相符的，即不包含j+1指向位置的元素
代码角度解释
注意，这里next数组中存的是 j 的值，不是 j+1的值
通过next数组我们可以找到最近一次满足 s[j+1] = s[i] 条件时，指针j+1的位置
前后缀不相等
前后缀不相等，那么指针 j+1要向前回退
前一位在next数组中对应的值，使用该值作为回退的依据，对应到图中就是让 j 等于next中当前位置（j+1指向的）前一位的值（也就是next[j]）
简单来说，就是从next数组中找到上次前后缀相等时指针 j+1指向的位置
while (j >= 0 && s[i] != s[j + 1] { // 前后缀不相同了
j = next[j]; // 向前回退
}
注意这里是要循环去回退，因为可能要回退多次，所以不能用 if
j >= 0）
整体代码：
void getNext(int* next, const string& s{
//初始化j和next数组
int j = -1;
next[0] = j;
//开始遍历模式串
for(int i = 1; i < s.size(; i++ { // 注意i从1开始
//如果没找到匹配值，使用next数组回退
while (j >= 0 && s[i] != s[j + 1] { // 前后缀不相同了
j = next[j]; // 不断地从next数组中找上次前后缀相等时指针 j+1指向的位置
}
//如果找到匹配值，j++(也就是把j+1往后移，并保存匹配值的位置(j值到next数组
if (s[i] == s[j + 1] { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
总结
实际上这样捋一遍可能还是有点乱，我认为原因之一是初始化的问题
但是只要记住一下几点应该还是能够想明白的：
1、两个指针 i 和 j 的定义
前缀末尾位置（不匹配值的前一个位置）
后缀末尾位置
2、遵循"循环不变量"原则
总是去找其前一个值所在位置下标在next数组中对应的记录值，然后由此回退到上次前后缀相等（s[i] == s[j + 1]）的位置
3、next数组存的是什么
最后一次前后缀相等的位置
实现 strStr(
实现 strStr( 函数。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr( 以及 Java的 indexOf( 定义相符。
思路
先求出needle 字符串（即 模式串）的next数组
如果值匹配，两个指针同时向后移动，不匹配则通过next数组返回上次匹配的位置，继续比较
1、实现getNext函数用于计算模式串前缀表
3、定义指针 j （规则要与计算next数组是保持一致，之前是-1，这里也要是-1）
从0开始遍历文本串
- 不匹配的就去next里找位置回退
- 匹配的，令 j 和 i 指针继续往下走（j后移就相当于j+1后移）
- 文本串指针i遍历到的当前位置减去模式串的长度（从0开始数的）再加1就可以得到文本串中出现模式串第一个字符的位置
代码
明确两个指针分别遍历的是谁
j 指针负责模式串；
i 指针负责文本串；
class Solution {
public:
//先定义计算next数组的函数
void getNext(int* next, string& s{
//初始化j和next数组
int j = -1;
next[0] = j;
//开始遍历模式串
for(int i = 1; i < s.size(; ++i{//注意i从1开始
//如果没找到匹配值，使用next数组回退
while(j >= 0 && s[j + 1] != s[i]{
j = next[j];//不断地从next数组中找上次前后缀相等时指针 j+1指向的位置
}
//如果找到匹配值，j++(也就是把j+1往后移，并保存匹配值的位置(j值到next数组
if(s[j + 1] == s[i]{
j++;
}
next[i] = j;//因为j已经++，利用i来把更新后的j值存到++之前下标对应的next中的位置
}
}
//使用next函数计算needle的前缀表
int strStr(string haystack, string needle {
//判断needle是否为空
if(needle.size( == 0{
return 0;
}
//定义一个数组作为next数组，长度与模式串相等
int next[needle.size(];
//计算needle的next数组
getNext(next, needle;
//定义指针j，因为我们计算next数组时j初始化为-1，这里也保持一致
int j = -1;
//开始遍历文本串
for(int i = 0; i < haystack.size(; ++i{
//判断是否匹配的代码与getNext中一致
while(j >= 0 && haystack[i] != needle[j + 1]{//不匹配时，从next数组找回退位置
j = next[j];
}
if(haystack[i] == needle[j + 1]{//匹配，i、j同时后移
j++;
}
//判断一下是否匹配结束
//因为j是用来遍历模式串的，如果j到达模式串尾部，那么说明文本串中出现了模式串，结束
if(j == needle.size( - 1{
//用文本串指针i遍历到的当前位置减去模式串的长度（从0开始数的）再加1就可以得到文本串中出现模式串第一个字符的位置
return (i - needle.size( + 1;
}
}
return -1;
}
};
看不明白请关闭网页，并骂一句2023.2.12 16:34分的我是傻逼，这都说不明白