rt.

本题我的做法是每次在往文本串拼接一个模式串的时候，再额外往后面加一个神秘字符来处理两个模式串在文本串上重叠的情况。

结果我加了个 # 就 WA 了，加了个 0 就 A 了。

萌新求助为什么/kel

WA：

https://www.luogu.com.cn/record/124563729。

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=5e6+5,M=26;
char s[N],t[N];
int trie[N][M],fail[N],cnt,n;
vector<int> ed[N];
void insert(char s[],int id) {
	int n=strlen(s+1),p=0;
	rep(i,1,n) {
		int ch=s[i]-'a';
		if(!trie[p][ch])
			trie[p][ch]=++cnt;
		p=trie[p][ch];
	}
	ed[p].push_back(id);
}
int in[N];
void build() {
	queue<int> q;
	rep(i,0,25) {
		if(trie[0][i])
			q.push(trie[0][i]);
	}
	while(!q.empty()) {
		int u=q.front(); q.pop(); ++in[fail[u]];
		rep(i,0,25) {
			if(trie[u][i])
				fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
			else
				trie[u][i]=trie[fail[u]][i];
		}
	}
}
int ans[N],f[N];
void query(char t[]) {
	int n=strlen(t+1),p=0;
	rep(i,1,n) {
		int ch=t[i]-'a';
		if(ch=='#') {
			p=0; continue;
		}
		p=trie[p][ch];
		++f[p];
	}
}
void toposort() {
	queue<int> q;
	rep(i,0,cnt) {
		if(!in[i])
			q.push(i);
	}
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(auto x:ed[u])
			ans[x]=f[u];
		int v=fail[u];
		f[v]+=f[u];
		if(!--in[v])
			q.push(v);			
	}
}
signed main() {
	scanf("%d",&n);
	int len=0;
	rep(i,1,n) {
		scanf("%s",s+1); insert(s,i);
		int m=strlen(s+1);
		rep(j,1,m)
			t[++len]=s[j];
		t[++len]='#';
	}
	build(); query(t); toposort();
	rep(i,1,n)
		printf("%d\n",ans[i]);
	return 0;
}

AC：

https://www.luogu.com.cn/record/124563786。

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=5e6+5,M=26;
char s[N],t[N];
int trie[N][M],fail[N],cnt,n;
vector<int> ed[N];
void insert(char s[],int id) {
	int n=strlen(s+1),p=0;
	rep(i,1,n) {
		int ch=s[i]-'a';
		if(!trie[p][ch])
			trie[p][ch]=++cnt;
		p=trie[p][ch];
	}
	ed[p].push_back(id);
}
int in[N];
void build() {
	queue<int> q;
	rep(i,0,25) {
		if(trie[0][i])
			q.push(trie[0][i]);
	}
	while(!q.empty()) {
		int u=q.front(); q.pop(); ++in[fail[u]];
		rep(i,0,25) {
			if(trie[u][i])
				fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
			else
				trie[u][i]=trie[fail[u]][i];
		}
	}
}
int ans[N],f[N];
void query(char t[]) {
	int n=strlen(t+1),p=0;
	rep(i,1,n) {
		int ch=t[i]-'a';
		if(ch=='0') {
			p=0; continue;
		}
		p=trie[p][ch];
		++f[p];
	}
}
void toposort() {
	queue<int> q;
	rep(i,0,cnt) {
		if(!in[i])
			q.push(i);
	}
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(auto x:ed[u])
			ans[x]=f[u];
		int v=fail[u];
		f[v]+=f[u];
		if(!--in[v])
			q.push(v);			
	}
}
signed main() {
	scanf("%d",&n);
	int len=0;
	rep(i,1,n) {
		scanf("%s",s+1); insert(s,i);
		int m=strlen(s+1);
		rep(j,1,m)
			t[++len]=s[j];
		t[++len]='0';
	}
	build(); query(t); toposort();
	rep(i,1,n)
		printf("%d\n",ans[i]);
	return 0;
}