题面：
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
原题链接：831. KMP字符串 - AcWing
核心：next 数组 - 最长相等前后缀
- next[i] 存储的就是使子串 p[0…i] 有最长相等前后缀的前缀的最后一位的下标[1]
- 时间复杂度：\(O(m+n)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int a[N], ne[N];
int main()
{
int n, m;
string p, s;
cin >> n >> p >> m >> s;
//构造模式串p的next数组
//next[i] 存储的就是使子串 p[0…i] 有最长相等前后缀的前缀的最后一位的下标
ne[0] = -1; //初始化 next 数组
for (int i = 1, j = -1; i < n; i++) {
//当p[j+1] != p[ne[j]+1]时，回退，直到j回到初始值-1
while (j != -1 && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1]) j++; //匹配成功，j移向p串下一位
ne[i] = j; //更新当前数i的next数组
}
//KMP
for (int i = 0, j = -1; i < m; i++) {
//匹配失败，j进行回退
while (j != -1 && s[i] != p[j + 1])
j = ne[j];
//匹配成功，j移向p串下一位，继续匹配
if (s[i] == p[j + 1]) j++;
if (j == n - 1) { //全部匹配完毕
cout << i - j << " "; //输出当前数组下标
j = ne[j]; //j回退至上一位，以便下次匹配
}
}
}