KMP用于优化字符串匹配，通过先对模式串操作，然后在模式串和主串比较的时候就会减少那些不必要的比较
操作就是计算模式串的subnext[]数组，subnext[j] 表示的是前 j-1 位这个子串里面， 前k个字符和后k个字符相等，subnext[j] 保存的就是这个k的最大值
KMP未优化版
原理
subnext[]创建
整体思路是借助j-1前面的值来计算第j位的subnext值
初始设置第0位的subnext值是-1，进入循环，使subnext[1]=0（第一位之前只有一位字符，首尾重复相同子串长度为0）
然后进入当j是普通的数的循环，如果第j位和第k位相同，说明在第j+1位的时候，前j位的k值为前j-1位的k减去1，如果sun[j]!=sun[k]，此时需要回溯第k位的那个subnext值，让sub[j]和sub[subnext[k]]比较，如果相等就让subnext[j+1]的值是subnext[k]+1
因为此时在比较第j位和第subnext[k]位的时候，也满足字符串前subnext[k]位和后subnext[k]位是重复的，如果还是不相等就继续回溯，直到无法回溯为止（k==-1）
主串和模式串的比较
利用上个函数我们设计的subnext数组，就能减少比较的次数，假设主串检索到第i位，模式串检索到第j位，如果这时候它俩不一样，就从j跳转到subnext[j]，因为这时候模式串的前subnext[j]位和后subnext[j]位字符是一样的，所以和主串的i-subnext[j]位字符也是一样的，就不用再比较了。如果pm或者ps有一个到头了，就停止比较
代码
#include<iostream>
#include<string>
using namespace std;
string m, sub;
int subnext[10000];
void creatnext()
{int j = 0; int k = -1; //k表示在前j-1个字符里前后缀相等的字符有k个subnext[0] = -1;while (j < sub.length()-1) //j表示在模式串遍历到的要求的那个next索引 由于最后一个字符与{if (k == -1 || sub[j] == sub[k]) //如果此时的k为负数要停止 避免越界访问//如果此时第j位等于第k位，说明继承k长度的首尾相同字符串成功{ j++; //此时可以算出来下一位也就是subnext[j+1]的值为k+1 （因为sub[j] == sub[k]多了一位）k++;subnext[j] = k;}else k = subnext[k]; //不然就继续回溯}
}
int main()
{getline(cin, m);getline(cin, sub);int pm = 0, ps = 0;int lm = m.length();int ls = sub.length();creatnext();while (pm < lm && ps < ls) {if (ps==-1 ||m[pm] == sub[ps]){pm++;ps++;}else ps = subnext[ps];}for (int i = 0; i < ls; i++)cout << subnext[i] << " ";cout << endl;if (ps == ls) cout << pm - ls;return 0;
}KMP优化版
原理
大体原理和之前那个一样，优化的就是判断 sub[k] 和 sub[subnext[k]]
假设子串 sub 为 "ABAB"，传统next数组的构建过程如下：
| 索引 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 字符 | A | B | A | B |
| next | -1 | 0 | 0 | 1 |
当 sub[3]（字符 B）匹配失败时，根据 next[3] = 1，会回溯到 sub[1]（字符 B）继续匹配。
但此时 sub[3] = B 和 sub[1] = B 字符相同，意味着即使回溯到 sub[1]，下一步仍然会匹配失败（因为 sub[1] 与原位置字符相同）。
举个例子
匹配到主串的a和模式串的c不符合，然后模式串就跳到第二位的c了，但是这个c和之前的c是一样的，还是不匹配，所以就重复比较了
这个时候就加入了那个优化， 比较当前这个字符和要跳回去的那个字符是不是相等的，如果相等那就回溯到上上个字符
if (sub[j] != sub[k]) {subnext[j] = k; }
else subnext[j] = subnext[k]; void creatnext() {int j = 0;int k = -1;subnext[0] = -1;while (j < sub.length() - 1) { // 注意循环到j < len-1if (k == -1 || sub[j] == sub[k]) {j++;k++;// 优化next数组if (sub[j] != sub[k]) {subnext[j] = k; } else subnext[j] = subnext[k]; //直接回溯上上个} else k = subnext[k]; }
}
