SP3267 DQUERY

Miku

[理论]（https://www.cnblogs.com/WAMonster/p/10118934.html）

感谢这位神仙帮助我深刻理解了莫队

      #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct t{
	int fail;
	int nex[26];
	int end;
}ac[1000001];
int cnt;
int l;
int p;
int x;
int ans;
int n;
string s;
queue <int>q;
void build(string s){
	l=s.length();
	p=0;
	for(int i=0;i<l;++i){
		x=s[i]-'a';
		if(!ac[p].nex[x]){
			cnt++;
			ac[p].nex[x]=cnt;
		}
		p=ac[p].nex[x];
	}
	ac[p].end+=1;//这就是个tire树 
}
void buildfail(){//找指针要 bfs 
	ac[0].fail=0;//0指自己 
	for(int i=0;i<26;++i){
		if(ac[0].nex[i]!=0){
			ac[ac[0].nex[i]].fail=0;
			q.push(ac[0].nex[i]);
		}//第二层也是 
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(ac[x].nex[i]!=0){
				ac[ac[x].nex[i]].fail=ac[ac[x].fail].nex[i];//失配指针寻找
				//为它失配指针指向的点的对应字母 
				q.push(ac[x].nex[i]);//改了就压，继续更新 
			}else{
				ac[x].nex[i]=ac[ac[x].fail].nex[i];//如果这个点是不存在的
				//那么直接指向失配指针对应点的对应点 
			}
		}	
	}
}
int query(string s){
	l=s.length();
	p=0;
	ans=0;
	for(int i=0;i<l;++i){
		x=s[i]-'a';
		p=ac[p].nex[x];
		for(int j=p;j&&ac[j].end!=-1;j=ac[j].fail){//跳跃，收集，清空 
			ans+=ac[j].end;
			ac[j].end=-1;
		}
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		cin>>s;
		build(s);
	}
	buildfail();
	cin>>s;
	cout<<query(s)<<endl;
	return 0;
}