KMP算法

懒得讲了，直接背吧（

用途：求字符串$p$是否在$s$中出现过。

时间复杂度：$O(|s|+|p|)$。

Ps：我们这里字符串下标从$0$开始计数。

大致思路：

如果是BF算法，那么失配了就算了（

但是如果是KMP算法的话，那么失配了就要跳到$f_{j-1}$上（代码称为fail）。

如果发现一个字符失配了，那么我们就要把$p$移到$p$中与失配字符相同的那一位，比如114514和1919810就要移到将114514的第一个1和1919810的第二个1重合。

而这个怎么移呢？答案就是$f$数组！

那么$f$数组怎么求呢？很简单，我们直接定义$f_i$是在第$i$位以前的离$i$最近的并且和$p_i$相同的字符的位置。

具体证明略（

然后就放个代码吧qwq

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1000001,inf=0x3f3f3f3f;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
string s,p;
int m,n,sa,fail[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>p;m=s.size(),n=p.size();
	int j=0;
	fs(i,1,n-1,1){
		while(j>0&&p[i]!=p[j]) j=fail[j-1];
		if(p[i]==p[j]) j++;
		fail[i]=j;	
	}
	j=0;
	fs(i,0,m-1,1){
		while(j>0&&s[i]!=p[j]) j=fail[j-1];
		if(s[i]==p[j]) j++;
		if(j==n){
			cout<<i-n+2<<'\n';
			//j=fail[j];
			j=fail[j-1];
		}	
	}
	fs(i,0,n-1,1) cout<<fail[i]<<' ';
	return 0;
}

Ps：这是洛谷模板的代码。