萌新刚学ACAM EPS秒玄关求条

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=2e6+5;
int n;
namespace AC{
	const int S=26;
    struct Trie{
    	int d;
    	int id;
    	int cnt;
    	int fail;
        int son[S];
        Trie(){
        	cnt=id=0;
        	memset(son,0,sizeof son);
        }
    }tr[M];
    int tot;
    int idc;
    int ans[N];
    void init(){
    	tot=idc=0;
    }
    int newnode(){
    	return ++tot;
    }
    void insert(string s,int &id){
    	int u=0;
    	for(char i:s){
    		if(!tr[u].son[s[i]-'a'])tr[u].son[s[i]-'a'];
    		u=tr[u].son[s[i]-'a'];
    	}
    	if(!tr[u].id)tr[u].id=++idc;
    	id=tr[u].id;
    }
    void build(){
    	queue<int>q;
    	for(int i=0;i<S;i++)if(tr[0].son[i])q.push(tr[0].son[i]);
    	while(!q.empty()){
    		int u=q.front();q.pop();
    		for(int i=0;i<S;i++){
    			 if(tr[u].son[i]){
    			 	tr[tr[u].son[i]].fail=tr[tr[u].fail].son[i];
    			 	tr[tr[tr[u].fail].son[i]].d++;
    			 	q.push(tr[u].son[i]);
    			 }else tr[u].son[i]=tr[tr[u].fail].son[i];
    		}
    	}
    }
    void query(string s){
    	int u=0;
    	for(char i:s){
    		u=tr[u].son[i-'a'];
    		tr[u].cnt++;
    	}
    }
    void topo(){
    	queue<int>q;
    	for(int i=0;i<=tot;i++)if(!tr[i].d)q.push(i);
    	while(!q.empty()){
    		int u=q.front();q.pop();
    		ans[tr[u].id]+=tr[u].cnt;
    		tr[tr[u].fail].d--;
    		if(!tr[tr[u].fail].d)q.push(tr[u].fail);
    	}
    }
}using namespace AC;
int id[N];
string t;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	string s;
    	cin>>s;
    	insert(s,id[i]);
    }
    build();
    cin>>t;
    query(t);
    topo();
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
    return 0;
}