KMP
原理
失败了退一步，再尝试
假设我们有一个字符串
暴力枚举法
假设 S[N] 是原串，P[M] 是模式串
for(int i = 1;i <= n;i++)
{
bool flag = true;
for(int j = 1;j <= m;j++)
{
if(s[i]!=p[j])
{
flag = false;
break;
}
}
}
在暴力做法中，若出现在匹配不合适的情况，只会将 匹配的起点往后移动一位
那么在我失败后，我新的模板串往后移动多少位可以开始匹配？
也就是我新的模板串往后移动多少位使得 我新的模板串从 起点到我上一次失败的点的串 和 原串相等
引入 next 数组
而 next[ i ] 的意义就是 ，以 i 为终点的后缀 和 从 1 开始的前缀相等，而且后缀的长度最长
假设 next[ i ] = j 那么其含义就是p[1,j] = p[i-j+1,i]
假设我们匹配出错的点是 i，对于模式串来说出错的点是 j+1，也就是 s[i] != p[j+1]，那么这个时候我们需要移动我们的模式串，也就是调用我们的next数组，找到以这个点为终点的后缀 和 从 1 开始的前缀，最长的相等，也就是 next[ j ]
模板
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
举例
假设有数组
S = " abababc"
P = "abababab"
那么我们有
next[1] = 0 //我不能等于自己
next[2] = 0 //ab 的前缀是 a，后缀是 b，不相等
next[3] = 1 //aba 长度是 1 的时候 前缀是 a，后缀是 a；长度是 2 的时候 前缀是 ab ，后缀是 ba，不匹配，所以 值为 1
next[4] = 2 //abab 长度为 2 的时候 前缀是 ab，后缀是 ab，长度为 3 的时候 前缀是 aba，后缀是 bab，不匹配，所以值为 2
依次类推
next[5] = 3
next[6] = 4
next[7] = 5
next[8] = 6
当我们进行 kmp 匹配的时候，当我们下标是 7 的时候不相等了【也就是 {s[7] = c} != {p[7]=a},i = 7,j = 6】
那么我找到 j = ne[j] == ne[6] = 4
为什么？
因为这个时候 是长度为6的字符串，他的前缀和后缀相等的最大 也就是 我们 next[6]的值也就是 4
练习
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106输入样例：
3 aba 5 ababa输出样例：
0 2
#include<iostream>
using namespace std;
const int N = 1e6+10;
int ne[N];
char s[N],p[N];
int n,m;
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> p + 1 >> m >> s + 1;
// 求 next 过程
for(int i = 2,j = 0;i <= n;i++)
{
while(j && p[i]!=p[j+1])
{
j = ne[j];
}
if(p[i]==p[j+1])
{
j++;
}
ne[i] = j;
}
// kmp 匹配过程
for(int i = 1,j = 0;i <= m;i++)
{
// j 没有退回起点 并且 s[i] 不能和 p[j+1] 匹配
while(j && s[i]!=p[j+1])
{
j = ne[j];
}
// 已经匹配
if(s[i]==p[j+1])
{
j++;
}
if(j == n)
{
//匹配成功
cout << i-n << " ";
j = ne[j];
}
}
return 0;
}