Contest1452 - [提高组(二)-字符串算法]-3.AC自动机

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;//ed[i]:这个节点是多少单词的结尾  
int tr[N][26],idx=1,ed[N],fk[N];
void insert(string t){
	int zz=0;
	for(int i=0;i<t.size();i++){
		int j=t[i]-'a';//字母映射下标 
		if(tr[zz][j]==0){
			tr[zz][j]=idx++;
		}
		zz=tr[zz][j];
	}//单词结尾  
	ed[zz]++;
}
void build(){
	queue<int> q;//为了层序遍历 
	for(int i=0;i<26;i++){
		if(tr[0][i]) q.push(tr[0][i]);
	} 
	while(q.size()){
		int f=q.front(); q.pop();
		for(int i=0;i<26;i++){
			int c=tr[f][i];//c child 子节点 
			if(c){//回  fk[] 
				fk[c]=tr[fk[f]][i];
				q.push(c);
			}else{//转移 tr[] 虚拟节点 
				tr[f][i]=tr[ fk[f] ][i];
			}
		}
	}
}
int main(){
	int n;
	cin>>n;
	while(n--){
		string t;
		cin>>t;
		insert(t);
	}
	build();
	
	string s;  int ans=0;
	cin>>s;
	int zz=0;
	for(int i=0;i<s.size();i++){
		zz=tr[zz][s[i]-'a'];
		for(int j=zz;j&&ed[j]!=-1;j=fk[j]){
			ans+=ed[j];
			ed[j]=-1;
		}
	}
	cout<<ans;
	return 0;
}