C++(g++ 7.5.0) 解法, 执行用时: 231ms, 内存消耗: 29664K, 提交时间: 2022-10-19 20:04:09

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

const int N=2e5+7,MOD=998244353;

char s[N],t[N];
int w[N],tr[N][26],len[N],pa[N],g[N],idx,fa[N],q,n;
vector<int>e[N];

int insert(){
	int m=strlen(t);
	int p=0;
	for(int i=0;i<m;i++){
		if(!tr[p][t[i]-'a'])tr[p][t[i]-'a']=++idx;
		p=tr[p][t[i]-'a'];
	}
	len[p]=m;
	return p;
}

void init(){
	queue<int>q;
	for(int i=0;i<26;i++){
		if(tr[0][i])q.push(tr[0][i]);
	}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(!tr[p][i])tr[p][i]=tr[fa[p]][i];
			else fa[tr[p][i]]=tr[fa[p]][i],q.push(tr[p][i]);
		}
	}
	for(int i=1;i<=idx;i++){
		e[fa[i]].push_back(i);
	}
}

void dfs(int u,int father){
	pa[u]=father;
	for(auto v:e[u]){
		if(w[u])dfs(v,u);
		else dfs(v,father);
	}
}

int main(){
	scanf("%s",s+1);
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int v;
		scanf("%s%d",t,&v);
		int p=insert();
		w[p]=(w[p]+v)%MOD;
	}
	init();
	dfs(0,0);
	g[0]=1,n=strlen(s+1);
	int p=0;
	for(int i=1;i<=n;i++){
		g[i]=g[i-1];
		p=tr[p][s[i]-'a'];
		for(int j=w[p]?p:pa[p];j;j=pa[j]){
			g[i]=(1ll*w[j]*g[i-len[j]]+g[i])%MOD;
		}
		printf("%d ",g[i]);
	}
	
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 330ms, 内存消耗: 24056K, 提交时间: 2022-09-26 21:14:41

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
int n,m,c,f[N],tr[N][26],fi[N],fr[N],e[N],g[N];
char s[N],t[N];
void ins(int w){
	int len=strlen(t+1),u=0;
	for (int i=1;i<=len;i++){
		if (!tr[u][t[i]-'a'])
			tr[u][t[i]-'a']=++c;
		u=tr[u][t[i]-'a'];
	}
	e[u]=w;g[u]=len;
}
void build(){
	queue<int>q;
	for (int i=0;i<26;i++)
		if (tr[0][i]) q.push(tr[0][i]);
	while(!q.empty()){
		int u=q.front();q.pop();
		if (e[u]) fr[u]=u;
		else fr[u]=fr[fi[u]];
		for (int i=0;i<26;i++)
			if (tr[u][i])
				fi[tr[u][i]]=tr[fi[u]][i],
				q.push(tr[u][i]);
			else tr[u][i]=tr[fi[u]][i];
	}
}
int main(){
	scanf("%s",s+1);n=strlen(s+1);
	scanf("%d",&m);
	for (int i=1,w;i<=m;i++)
		scanf("%s%d",t+1,&w),ins(w);
	build();f[0]=1;
	for (int i=1,u=0;i<=n;i++){
		f[i]=f[i-1];u=tr[u][s[i]-'a'];
		for (int x=fr[u];x;x=fr[fi[x]])
			if (g[x]<=i) (f[i]+=1ll*f[i-g[x]]*e[x]%P)%=P;
        printf("%d%c",f[i],i<n?' ':'\n');
	}
	return 0;
}