RT

感觉自己写的很对啊/kk

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5,SUM=30,MAXL=2e6+5;
ll n;
struct ACAM{
	ll trie[MAXN*SUM][SUM],tot;
	ll fail[MAXN*SUM],in[MAXN*SUM];
	ll cnt[MAXN*SUM],ans[MAXN];
	vector<ll> idx[MAXN*SUM];
	void insert(char *s,ll id){
		ll now=0;
		for(int i=1;s[i];i++){
			if(!trie[now][s[i]-'a'+1])trie[now][s[i]-'a'+1]=++tot;
			now=trie[now][s[i]-'a'+1];
		}
		idx[now].push_back(id);
		return;
	}
	queue<ll> q;
	void build(){
		for(int i=1;i<=26;i++)if(trie[0][i])q.push(trie[0][i]);
		while(q.size()){
			ll now=q.front();
			q.pop();
			for(int i=1;i<=26;i++){
				if(trie[now][i]){
					fail[trie[now][i]]=trie[fail[now]][i];
					in[trie[fail[now]][i]]++;
					q.push(trie[now][i]);
				}
				else trie[now][i]=trie[fail[now]][i];
			}
		}
		return;
	}
	void query(char *s){
		ll now=0;
		for(int i=1;s[i];i++){
			now=trie[now][s[i]-'a'+1];
			cnt[now]++;
		}
		return;
	}
	void solve(){
		for(int i=0;i<=tot;i++)if(in[i]==0)q.push(i);
		while(q.size()){
			ll now=q.front();
			q.pop();
			cnt[fail[now]]+=cnt[now];
			in[fail[now]]--;
			if(!in[fail[now]])q.push(fail[now]);
		}
		for(int i=0;i<=tot;i++)if(idx[i].size())for(ll x:idx[i])ans[x]=cnt[i];
		for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
		return;
	}
}acam; 
char ch[MAXL];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>(ch+1);
		acam.insert(ch+1,i);
	}
	acam.build();
	cin>>(ch+1);
	acam.query(ch+1);
	acam.solve();
	return 0;
}