题目传送门
思路：
首先我们要学习一下 \(KMP\) 算法，不会的可以看这个大佬的文章
那么我们就直接开始讲思路了。
针对于每一位，\(kmp\) 算法已经预处理出了一个对应 \(kmp\) 数组的单元，映射着如果此位失配，它可能的最靠后的一个重新开头是哪一个。
让我们举一个例子：假如让 \(aaab\) 与 \(aab\) 匹配。一开始，\(aab\) 的 \(aa\) 与 \(aaab\) 的开始的 \(aa\) 成功匹配，但到了第三位失配了。此时，朴素算法会跳出，找到下一个开头进行比对。然而 \(kmp\) 算法用 \(next\) 数组得知，这位失配后应该可能却可以与第二位匹配成功，而又成功，于是又继续往后匹配，然后就匹配成功了，只比较了 \(5\) 次，比 \(O(n^2)\) 好了不少。
时间复杂度：\(O(m+n)\)
注意了
此题有坑。
喜欢直接用算法中的名称定义数组的要小心了。
在 \(windows\) 操作系统中的
int next[];
是没有问题的。
但是，在 \(Linux\) 系统中，\(next\) 是一个系统函数。
所以，在使用 \(Linux\) 系统的评测机中定义一个叫 \(next\) 的容器，会 \(CE\)，也就是编译错误。
ps：这可是我十几次 \(CE\) 的血汗教训啊！
next表实现模板
//用string类型也可以
char a[1000010]; // 文本串
char b[1000010]; // 模板串(将被匹配的子串)
int kmp_next[1000010]; // next数组
void getNext(int m){
int j = 0;
// 初始化next[0]的值
kmp_next[0] = 0;
for(int i=1; i<m; ++i){
// 当这一位不匹配时，将j指向此位之前最大公共前后缀的位置
while(j>0 && b[i]!=b[j]) j=kmp_next[j-1];
// 如果这一位匹配，那么将j+1，继续判断下一位
if(b[i]==b[j]) ++j;
// 更新next[i]的值
kmp_next[i] = j;
}
}
Code：
#include <bits/stdc++.h>
using namespace std;
char a1[2000005],a2[2000005];
int kmp[2000005];
int main()
{
scanf("%s%s",a1,a2);
kmp[0]=kmp[1]=0;//前一位，两位失配了，都只可能将第一位作为新的开头
int len1=strlen(a1),len2=strlen(a2);
int k;
k=0;
for(int i=1;i<len2;i++)//自己匹配自己
{
while(k&&a2[i]!=a2[k])
{
k=kmp[k];//找到最长的前后缀重叠长度
}
kmp[i+1]=a2[i]==a2[k]?++k:0;//不相等的情况，即无前缀能与后缀重叠，直接赋值位0（注意是给下一位，因为匹配的是下一位适失配的情况）
}
k=0;
for(int i=0;i<len1;i++)
{
while(k&&a1[i]!=a2[k])
{
k=kmp[k];//如果不匹配，则将利用kmp数组往回跳
}
k+=a1[i]==a2[k]?1:0;//如果相等了，则匹配下一位
if(k==len2)
{
printf("%d\n",i-len2+2);//如果已经全部匹配完毕，则输出初始位置
}
}
for(int i=1;i<=len2;i++)
{
printf("%d ",kmp[i]);//输出f数组
}
return 0;
}