C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 20952K, 提交时间: 2022-10-25 20:14:56

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6,M=998244353,P=99824353;
using ll=long long;
char A[N],B[N];
int a[N],_b,pw[N],n,m,L[N],f[N],g[N];
int gs(int l,int r){
	return (a[r]+M-ll(a[l-1])*pw[r-l+1]%M)%M;
}
int main(){
	scanf("%s%s",A+1,B+1);
	n=strlen(A+1),m=strlen(B+1);
	if(n<m){puts("0");return 0;}
	int i,x,y;
	for(i=pw[0]=1;i<=n;++i)pw[i]=41719ll*pw[i-1]%M;
	for(x=1;x<=n;++x)a[x]=(41719ll*a[x-1]+A[x])%M;
	for(x=1;x<=m;++x)_b=(41719ll*_b+B[x])%M;
	for(x=1;x<=n-m+1;++x)
		if(gs(x,x+m-1)==_b)
			L[x+m-1]=x;
	for(x=1;x<=n;++x)if(L[x]<L[x-1])L[x]=L[x-1];
	f[0]=g[0]=1;
	for(x=1;x<=n;++x){
		if(L[x])f[x]=g[L[x]-1];
		f[x]=(ll(f[x])+f[x-1])%P;
		g[x]=(ll(g[x-1])+f[x])%P;
	}printf("%d\n",f[n]);
	return 0;
}

C++(clang++11) 解法, 执行用时: 32ms, 内存消耗: 17016K, 提交时间: 2021-03-06 19:34:32

#include<bits/stdc++.h>
//maddison10
using namespace std;

const int mxn=1e6+5,mdn=99824353;

int n,m;
int net[mxn],f[mxn],g[mxn],p[mxn],rr[mxn];
char s[mxn],t[mxn];

int main(){
	scanf("%s",s+1);scanf("%s",t+1);
	n=strlen(s+1);m=strlen(t+1);
	for(int i=2,j=0;i<=m;i++){
		while(j&&t[i]!=t[j+1])j=net[j];
		if(t[i]==t[j+1])j++;
		net[i]=j;
	}
	for(int i=1,j=0,ps=0;i<=n;i++){
		while(j&&s[i]!=t[j+1])j=net[j];
		if(s[i]==t[j+1])j++;
		if(j==m)ps=i-m+1,j=net[j];
		rr[i]=ps;
	}

	f[0]=g[0]=1;
	for(int i=1;i<=n;i++){
		if(rr[i])f[i]=(1ll*g[rr[i]-1]*rr[i]%mdn-p[rr[i]-1]%mdn+mdn)%mdn;
		g[i]=(g[i-1]+f[i])%mdn;
		p[i]=(p[i-1]+1ll*f[i]*i%mdn)%mdn;
	}
	cout<<g[n]<<'\n';
	return 0;
}