P3375 【模板】KMP字符串匹配

$A\mathrm{.}size()==n>=B\mathrm{.}size()==mA.size()==n>=B.size()==m$

定义完全匹配函数：$P(x)={\sum }_{i=0}^{m-1}[B(i)-A(x-m+1+i){]}^2\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{[B(i)-A(x-m+1+i)\backslash \; ]^2\}\}$

则有$P(x)={\sum }_{i=0}^{m-1}[B(i{)}^2+A(x-m+1+i{)}^2-2\ast B(i)\ast A(x-m+1+i)]\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{[B(i)^2+A(x-m+1+i)^2-2*B(i)*A(x-m+1+i)]\}\}$

设多项式$S(i)=B(m-1-i),g=A\ast SS(i)=B(m-1-i),g=A*S$，则$B(i)=S(m-1-i)B(i)=S(m-1-i)$

那么$P(x)={\sum }_{i=0}^{m-1}S(i{)}^2+{\sum }_{i=0}^{m-1}A(x-m+1+i{)}^2-2\ast g(x)\{P(x)=\backslash sum\_\{i=0\}^\{m-1\}\{S(i)^2\}+\backslash sum\_\{i=0\}^\{m-1\}\{A(x-m+1+i)^2\}-2*g(x)\}$

$P(x)==0P(x)==0$表示A串中以$A(x)A(x)$结尾长度为$mm$的子串和$BB$串匹配

然后用$NTTNTT$计算多项式$gg$

这一题还需要再输出一行$BB$串的$NextNext$数组。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=(1<<21)+7,mod=998244353;
inline int qpow(int x,int y) {
	int res(1);
	while(y) {
		if(y&1) res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int r[maxn];
inline void ntt(int *x,int lim,int opt) {
	int i,j,k,m,gn,g,tmp;
	for(i=0; i<lim; ++i)
		if(i<r[i]) swap(x[i],x[r[i]]);
	for(m=2; m<=lim; m<<=1) {
		k=m>>1;
		gn=qpow(3,(mod-1)/m);
		for(i=0; i<lim; i+=m) {
			g=1;
			for(j=0; j<k; ++j,g=1LL*g*gn%mod) {
				tmp=1LL*x[i+j+k]*g%mod;
				x[i+j+k]=(x[i+j]-tmp+mod)%mod;
				x[i+j]=(x[i+j]+tmp)%mod;
			}
		}
	}
	if(opt==-1) {
		reverse(x+1,x+lim);
		int inv=qpow(lim,mod-2);
		for(i=0; i<lim; ++i) x[i]=1LL*x[i]*inv%mod;
	}
}
int A[maxn],B[maxn],f[maxn/2],Next[maxn/2],n,m,k,lim(1);
char a[maxn/2],b[maxn/2];
void getfail() {
	Next[0]=Next[1]=0;
	for(int i=1,j;b[i];++i) {
		j=Next[i];
		while(j&&b[i]!=b[j]) j=Next[j];
		Next[i+1]=(b[i]==b[j])?j+1:0;
	}
}
int main() {
	scanf("%s%s",a,b);
	n=strlen(a),m=strlen(b);//n>m
	while(lim<(n<<1)) lim<<=1;
	for(int i=0; i<lim; ++i) r[i]=(i&1)*(lim>>1)+(r[i>>1] >> 1);
	for(int i=0;i<n;++i) A[i]=a[i]-'a'+1;
	for(int i=0;i<m;++i) B[i]=b[m-1-i]-'a'+1;
	int sum(0);
	for(int i=0;i<m;++i) sum+=B[i]*B[i];
	f[0]=A[0]*A[0];
	for(int i=1;i<n;++i) f[i]=f[i-1]+A[i]*A[i];
	ntt(A,lim,1),ntt(B,lim,1); 
	for(int i=0; i<lim; ++i) A[i]=1LL*A[i]*B[i]%mod;
	ntt(A,lim,-1);
	vector<int>ans;
	for(int i=m-1;i<lim;++i) {
		int p=f[i]-f[i-m]-2*A[i]+sum;
		if(!p) ans.emplace_back(i-m+2);
	}
//	cout<<ans.size()<<'\n';
	for(int i:ans) {
		cout<<i<<'\n';
	}
	getfail();
	for(int i=1;i<=m;++i) cout<<Next[i]<<' ';
	return 0;
}