12分球条

#include<bits/stdc++.h>
using namespace std;
string s;
int ch[500050][26],cnt[500050],idx,nxt[500050],ans[500050],g[500050],du[500050],pidx;
void insert(int &op){
	s+='\0';
	int p = 0,u;
	for(int i = 0;s[i];i++){
		u = s[i]-'a';
		if(!ch[p][u])ch[p][u] = ++idx;
		p = ch[p][u];
	}
	if(!cnt[p])cnt[p] = ++pidx;
	op = cnt[p];
}
void BFS(){
	queue<int>q;
	for(int i = 0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
	int u;
	while(!q.empty()){
		u = q.front();
		q.pop();
		for(int i = 0;i<26;i++){
			if(ch[u][i]){
				nxt[ch[u][i]] = ch[nxt[u]][i];
				du[ch[nxt[u]][i]]++;
				q.push(ch[u][i]);
			}
			else ch[u][i] = ch[nxt[u]][i];
		}
	}
}
void query(){
	s+='\0';
	int p = 0;
	for(int i = 0;s[i];i++){
		p = ch[p][s[i]-'a'];
		ans[p]++;
	}
}
void topu(){
	queue<int>q;
	for(int i = 0;i<=idx;i++)if(du[i]==0)q.push(i);
	int u,v;
	while(!q.empty()){
		u = q.front();
		q.pop();
		ans[cnt[u]] = ans[u];
		v = nxt[u];
		ans[v]+=ans[u];
		if(!--du[v])q.push(v);
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	memset(ch,0,sizeof(ch));
	memset(nxt,0,sizeof(nxt));
	memset(cnt,0,sizeof(cnt));
	memset(ans,0,sizeof(ans));
	memset(g,0,sizeof(g));
	memset(du,0,sizeof(du));
	idx = pidx = 1;
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>s;
		insert(g[i]);
	}
	BFS();
	cin>>s;
	query();
	topu();
	for(int i = 1;i<=n;i++)cout<<ans[g[i]]<<'\n';
	return 0;
}