【模板】AC 自动机

posted on 2022-06-11 11:17:10 | under 模板 | source

template<int N,int M=26,int D='a'> struct acam{
	int ch[N+10][M],cnt[N+10],tot,fail[N+10];
	int sum[N+10],inn[N+10];
	int newnode(){return ++tot,cnt[tot]=fail[tot]=0,memset(ch[tot],0,sizeof ch[tot]),tot;}
	acam():tot(-1){newnode();}
	int insert(char *s){
		int len=strlen(s+1),u=0;
		for(int i=1;i<=len;i++){
			int &v=ch[u][s[i]-D];
			v?u=v:u=v=newnode();
		}
		return cnt[u]++,u;
	}
	void build(){
		queue<int> q;
		for(int i=0;i<M;i++) if(ch[0][i]) q.push(ch[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<M;i++){
				if(ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
				else ch[u][i]=ch[fail[u]][i];
			}
		}
	}
//	int query(char *s){
//		memset(vis,0,sizeof vis);
//		int len=strlen(s+1),u=0,res=0;
//		for(int i=1;i<=len;i++){
//			u=ch[u][s[i]-D];
//			for(int v=u;v&&!vis[v];v=fail[v]){
//				res+=cnt[v],vis[v]=1;
//			}
//		}
//		return res;
//	}
	void query(char *s){
		memset(sum,0,sizeof sum);
		memset(inn,0,sizeof inn);
		queue<int> q;
		int len=strlen(s+1),u=0;
		for(int i=1;i<=len;i++) sum[u=ch[u][s[i]-D]]++;
		for(int u=1;u<=tot;u++) inn[fail[u]]++;
		for(int u=1;u<=tot;u++) if(!inn[u]) q.push(u);
		while(!q.empty()){
			int u=q.front();q.pop();
			int v=fail[u];
			sum[v]+=sum[u];
			if(!--inn[v]&&v) q.push(v);
		}
	}
};