KMP算法
为什么叫做KMP呢。
因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP
next数组就是一个前缀表（prefix table）。
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
前缀表是如何记录的呢？
首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置
前缀表
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
aabaaf
前缀
a
aa
aab
aabaa
aabaaf 不是
后缀
f
af
aaf
baaf
abaaf
aabaaf 不是
求最长相等前后缀长度
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaaf 0
得出前缀表
aabaaf
010120
**为什么最长相等前后缀，开始，就能继续匹配其他的？**
因为如果我算出了前缀和后缀是相等的话，那么我第一次在匹配前缀的时候，其实已经完成了后缀的部分匹配工作。 举个例子：原串aabaabaaf，模式串aabaaf 一开始从第一个a匹配到第二个a的同时，实际上已经完成了从第四个a到第五个a的匹配过程，但是必须知道是模式串的前后缀部分相同，模式串第二个aa的匹配就可以省去了，就可以直接让原串的第二个b和模式串的b匹配成功了
next数组
放的也是前缀表,会对前缀表调整
next数组实际上可以自减一或者前移一处理，不同的编码习惯导致的
a a b a a f0 1 0 1 2 0
-1 0 1 0 1 2 //右移 //遇见冲突,就找冲突的位置所对应的下标
-1 0 -1 0 1 -1 //整体减一 //遇见冲突,就找冲突的前一位所对应的下标加1
1.前后缀相等
2.前后缀不同
3.更新
void getNext(int* next, const string& s){int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i从1开始while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后缀j++;}next[i] = j; // 将j（前缀的长度）赋给next[i]}
}
KMP算法的前缀next数组最通俗的解释，如果看不懂我也没辙了_next数组是针对-CSDN博客
a a a b（索引 0~3）
| 字符索引 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 字符 | a | a | a | a |
| next | -1 | 0 | 1 | 2 |
-
初始化：
next[0] = -1（第一个字符无前缀和后缀）
-
计算
next[1]（字符a，索引 1）：- 前一个字符的
next值为next[0] = -1，比较P[1]和P[-1 + 1] = P[0]（即第一个a）。 P[1] = a与P[0] = a相等 →next[1] = next[0] + 1 = -1 + 1 = 0。
- 前一个字符的
-
计算
next[2]（字符a，索引 2）：- 前一个字符的
next值为next[1] = 0，比较P[2]和P[j + 1] = P[1]（即第二个a）。 - 前面的是1，**说明前面的字符已经和第一个相等了
P[2] = a与P[1] = a相等 →next[2] = next[1] + 1 = 0 + 1 = 1。- 对称性累加了
- 前一个字符的
-
计算
next[3]（第四个a，索引 3）：- 前一个字符的
next值为next[2] = 1，比较P[3]和P[1 + 1] = P[2]（第三个a）。 - 匹配成功 →
next[3] = next[2] + 1 = 1 + 1 = 2。
- 前一个字符的
| 字符索引 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 字符 | a | a | a | b |
| next | -1 | 0 | 1 | 0 |
-
计算
next[3]（字符b，索引 3）：- 前一个字符的
next值为next[2] = 1，比较P[3]和P[1 + 1] = P[2]（即第三个a）。 P[3] = b与P[2] = a不相等，需要回溯：- 回溯到
j = next[1] = 0，比较P[3]和P[0 + 1] = P[1] = a→ 仍不相等。 - 继续回溯到
j = next[0] = -1，比较P[3]和P[-1 + 1] = P[0] = a→ 仍不相等。 - 最终
j = -1→next[3] = -1 + 1 = 0。
—>
- 回溯到
- 前一个字符的
a. 求得是最长相等前后缀长度
如果找到了相同的前后缀 当前面字符串(不包括当前字符)的最长前后缀长度下标的字符 与 当前的字符相等时结果为 j++ , next[i]=j(匹配的字符个数加1);如 a a a a 计算 next[3]（第四个 a时)，前面的最长前后缀长度为2 前缀和后缀为(aa)若要继承下它的对称性 那么后缀为(aa a) ,前缀也要为(aa a) 即 当前字符(s[i]) 要等于 最长前后缀长度下标的字符(s[j+i]) a a (a) a 与 a a a (a)(由于我使用了减一操作 所以为 j+1 , 最后若是相等了说明最长前后缀长度+1, 若索引从1开始算也就是最长前后缀长度的下一位下标字符)为何可以继承对称性 前缀有 a0 aa01 aaa012 注意要求的是最长相等前后缀长度 不是相等的前后缀个数后缀有 a3 aa23 aaa123 那么前面的最长前后缀长度为正数 说明 (aa) a a 要可以与 a (aa) a 匹配 那么只要(aaa)a和a(aaa)即可继承对称性故只要相同的前后缀 即可继承对称性 (j+1)
b. 当前面字符的前一个字符的对称程度为0的时候,说明前一个字符与第一个字符相同, 同对称程度为n时,前一个字符 到该字符前n位a (aa) a 与 第一位字符到第一位字符后n位(aa) a a相同
d. 那么只要匹配第一位字符的后n位的下一位字符是否与当前字符相同,那么就可以对称性+1
e. j记录的是前缀和后缀的长度 也就是 s[ j ] 为 相同的前后缀 的前缀最后一个字符
c. 当前后缀不相同了 (通过递推逻辑保证前后缀的匹配性)
若是前后缀不相同了 需要不断向前回退 回退的目的就是找到可以继承的对称性 也就是找到相同的前后缀
`next[j]` 的定义是：**子串 `s[0..j-1]` 的最长相等真前缀和后缀的长度**。(aa) a aa a (aaa) b 不对
回溯到j = next[j] = 0就是返回到当前已匹配更短的前缀 (aa) a a b 与 a a (aa) b ,比较P[3]和 `P[0 + 1] = P[1] a(a) aa aa a(b)
由于next[j] 说明 没有b时 aa ab有相等前后缀 ,那么表明是前缀s[0~j] 与 后缀s[(i - j)~ (i-1)]已知为何可以回退再找相同的前后缀
前缀是从前到后的 都是从左到右顺序
后缀是从后到前的 那么只要存在前面的最长前后缀长度为正数,就说明存在前缀和的后缀(不包括当前字符下的后缀)可以匹配 (a )a a b 与 a a (a)b
然后 (a a) aa b 与 a a (aab) s[i] != s[j + 1] 确定是否要接着回退 , 若找不到就是不存在 , j 为-1 (会返回到next[0])当i=3时，next[3]=2确保s[0…1]=s[1…2]，当i=4时，回退到j=1，前缀s[0…1]必须与s[2…3]匹配，因为此时处理的是更长的子串，而后缀的起始位置由i和j共同决定。
- 为什么
s[0..1]必须与s[2..3]匹配？next[3] = 2已保证s[0..1]与s[1..2]匹配。。- 当处理前 4 个字符
"aaaa"时，后缀范围从s[1..2]扩展为s[2..3]（因为子串长度从 3 变为 4）。 - 由于前 3 个字符的后缀
s[1..2]已匹配前缀s[0..1]，
关键：由于s[3]的值与s[1]相同（均为'a'），因此s[2..3] = "aa"必然与s[0..1] = "aa"匹配。
呃呃呃呃呃 ,感觉还是有点模糊,s[0..1] 与 s[2..3] 匹配
使用next数组来做匹配
如果我们在后缀的后面不匹配了,就在与其相等的前缀的后面继续开始匹配
012345
aabaaf
010120前缀的后面的下标正好是前缀的长度
也就是从b开始重新匹配
定义两个下标j 指向模式串起始位置，i指向文本串起始位置。
int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始while(j >= 0 && s[i] != t[j + 1]) { // 不匹配j = next[j]; // j 寻找之前匹配的位置}if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动j++; // i的增加在for循环里}if (j == (t.size() - 1) ) { // 文本串s里出现了模式串treturn (i - t.size() + 1);}
}
代码
class Solution {
public:vector<int> get_Next(string needle){vector<int> next(needle.size(),0);next[0]=-1;int j=-1;for(int i=1;i<needle.size();i++){while(needle[i]!=needle[j+1]&&j>=0){j=next[j];}if(needle[i]==needle[j+1]){j++;}next[i]=j;}return next;}int strStr(string haystack, string needle) {if(needle.size()==0)return 0;vector<int> next = get_Next(needle);int j=-1;for(int i = 0;i<haystack.size();i++){while(j >= 0 && haystack[i] !=needle[j + 1]) j=next[j];if(needle[j+1]==haystack[i])j++; if(j==needle.size()-1) return (i - needle.size()+1);}return -1;}};
力扣题目链接 https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
