rt
题目
WA on test2
test2与test1的区别是n不为1 求调qwq

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
	int vis[27];//子节点 
	int fail;//失配指针 
	int end;
}p[N];
int cnt;//trie树当前节点编号 
inline void built(string s){//trie树建树 
	int l=s.length();
	int now=0;
	for(int i=1;i<=l;i++){
		if(p[now].vis[s[i]-'a']==0){
			p[now].vis[s[i]-'a']=++cnt;
		}
		now=p[now].vis[s[i]-'a'];
	}
	p[now].end++;
}
void get_fail(){//构建失配指针 
	queue<int>q;
	for(int i=0;i<=26;i++){//压入所有第二层节点 
		if(p[0].vis[i]!=0){
			p[p[0].vis[i]].fail=0;
			q.push(p[0].vis[i]);
		}
	}
	while(!q.empty()){//bfs 
		int u=q.front();
		q.pop();
		for(int i=0;i<=26;i++){
			if(p[u].vis[i]!=0){
				p[p[u].vis[i]].fail=p[p[u].fail].vis[i];
				q.push(p[u].vis[i]);
			}else{
				p[u].vis[i]=p[p[u].fail].vis[i];
			}
		}
	}
}
int query(string s){//查询 
	int l=s.length();
	int now=0,ans=0;
	for(int i=1;i<=l;i++){
	    now=p[now].vis[s[i]-'a'];
	    for(int t=now;t&&p[t].end!=-1;t=p[t].fail){
	        ans+=p[t].end;
	        p[t].end=-1;
	    }
	}
	return ans;
}
int main(){
	int n;
	string s,t;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		built(s);
	}
	p[0].fail=0;
	get_fail();
	cin>>t;
	cout<<query(t)<<endl;
	return 0;
}