给定一个字符串 SS，以及一个模式串 PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 PP 在字符串 SS 中多次作为子串出现。
求出模式串 PP 在字符串 SS 中所有出现的位置的起始下标。
输入格式
第一行输入整数 NN，表示字符串 PP 的长度。
第二行输入字符串 PP。
第三行输入整数 MM，表示字符串 SS 的长度。
第四行输入字符串 SS。
输出格式
共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。
数据范围
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106输入样例：
3 aba 5 ababa输出样例：
0 2
难度：简单 时/空限制：1s / 256MB 总通过数：71523 总尝试数：139139 来源：模板题 算法标签
挑战模式
核心思路：我们使用S表示我们的主串，P表示我们的模式串
- 首先我们联想字符串的暴力做法，我们使用i指针表示我们当前主串的位置，使用j指针表示我们当前模式串的位置。我们可以发现我们匹配的时候可以保持i指针不动，然后我们的j指针回退到P串的刚开始的位置就好了。但是这样我们会发现时间复杂度是很高的，也就是一个\(n^2\)的级别.
- 然后我们会想怎么进行优化呢。我们会发现一个很重要的点，就是其实我们每次没有必要回退到刚开始的位置。于是我们引入ne数组，首先我们得清楚他的定义：它表示的是P[1,i]中相等的前后缀的最长长度.接下来就是怎么去求这么一个数组。至于为什么不需要回退到刚开始的位置，可以看下我举的例子：
1 2 3 4 5
S: a b a b a
P: a b a b c
我们可以看到当最后的位置不匹配的时候，也就是P[j+1]!=S[i].j=ne[j],也就是回退到2，然后P[j+1]再与S[i]比较，为什么可以这样呢，我们可以使用反证法。因为既然可以匹配到最后一个位置，那说明前面几个位置那必然是可以匹配的。所以必然是存在一段长度L是可以回退的。我们可以知道j回退到2其实与S中的字符串匹配的也就是以3为首的字符串开始。一定不要忘了我们的目的：我们是要从S中找到与P相匹配的位置.
下面先看一个基本的模拟样例：
我们可以知道ne数组的前后缀再匹配的时候。要么相等，那么这个值就会加1。不相等那我们是可以回退的：j=ne[j].这句话的意思是找到之前可以匹配的位置。我们需要知道求ne数组和我们最后的S和P的匹配是一样的，本质都是退而求其次的过程。所以代码都是大同小异的.下面我重点解释一下为什么每次都是j+1.因为我们需要到ne数组回退的位置前一个去匹配:
1 2 3 4 5
S: a b a b a
P: a b a b c
就拿这个例子举例，当我们发现到i=5的时候j需要回退，要注意这个时候j是4，回退之后是2。很显然我们需要j+1=3这个位置继续去匹配。因为我们的S[34]已经等于了P[12].要注意我们的i还是5并没有回退哦。
知道这个了也就知道为什么j需要从0开始了，因为j+1正好指向P[1].还有一个初始值需要注意那就是ne[1]=0,因为只有一个字符他是没有前后缀的.所以我们的i从2开始枚举.
解释了ne数组怎么来的，自然也就知道了接下来的KMP匹配这是大同小异的.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6e6+10;
int m, n;
char s[N], p[N];
int ne[N];
int main()
{
cin >> n >> p + 1;
cin >> m>>s+1;
ne[1] = 0;//初始化
for (int i = 2, j = 0;i <= n;i++)//其实我们可以把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 <= m;i++)
{
while (j && s[i] != p[j + 1])
{
j = ne[j];
}
if (s[i] == p[j + 1])
{
j++;
}
if (j == n)
cout << i - n << " ";//因为我们需要找的是刚开始的位置，这已经超过n个单位的长度了,因为这下标是从0开始所以不需要加1
}
}