基础
下文的字符串下标皆从 \(1\) 开始。
考虑定义一个数组 \(ne_i\)，指的是设字符串 \(t\) 的前 \(i\) 位为 \(s\)。字符串 \(s\) 的前 \(ne_i\) 位与后 \(ne_i\) 位完全相同，且 \(ne_i\) 取到了最大值，并且 \(ne_i\) 不为字符串 \(s\) 的长度。
是不是觉得很绕？我们举一个例子来更好的说明：
考虑 \(t\) 为 abababc。那么 \(ne\) 数组为 \(0,0,1,2,3,4,0\)。
然后我们考虑如何快速求出 \(ne\) 数组。暴力枚举当然是一种方案，但是复杂度我们不能接受，于是我们考虑优化。
有一个显然的结论，\(ne_{i+1}-ne_i\le 1\)，这个就不证明了。
于是我们可以分类讨论，对 \(t_{i+1}\) 是否等于 \(t_{{ne_i}+1}\) 进行分类。
-
相等，此时 \(ne_{i+1}={ne_i}+1\)。
-
否则，我们考虑令 \(j=ne_{ne_i}\)，判断 \(t_{j+1}\) 是否等于 \(t_{i+1}\) 并重复这一过程。
为什么在否则时我们的做法是正确的，可以看一下图：
然后这样做的时间复杂度是线性的，可以看一下题目。
题目
KMP
板子题，可以直接看一下代码：
#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int ne[N],j,len1,len2;
char s1[N],s2[N];
signed main(){
cin>>(s1+1)>>(s2+1);
len1=strlen(s1+1);len2=strlen(s2+1);
for(int i=2;i<=len2;i++){
while(j&&s2[i]!=s2[j+1])j=ne[j];
if(s2[i]==s2[j+1])j++;
ne[i]=j;
}
j=0;
for(int i=1;i<=len1;i++){
while(j&&s1[i]!=s2[j+1])j=ne[j];
if(s1[i]==s2[j+1])j++;
if(j==len2){
cout<<i-len2+1<<'\n';
j=ne[j];
}
}
for(int i=1;i<=len2;i++)cout<<ne[i]<<' ';
return 0;
}