ac自动机求查错
查看原帖
ac自动机求查错
198964
Msents楼主2022/1/26 16:21
#include<bits/stdc++.h>
using namespace std;
const int CharMax=128;
const int Nmax=1000005;
struct trieNode{
	int ch[CharMax];
	int count,failch;
}trie[Nmax*2];
int trieCnt=0;
void Insert(string &str){
	int now=0;
	for(int i=0;i<(int)str.length();i++){
		if(!trie[now].ch[(int)str[i]])trie[now].ch[(int)str[i]]=++trieCnt;
		now=trie[now].ch[(int)str[i]];
	}
	trie[now].count++;
}
void FailBFS(){
//	struct BFSNode{
//		int data,pre;
//		char ch;
//	};
//	queue<BFSNode>q;
//	q.push(BFSNode{0,0,'#'});
//	trie[0].failch=0;
//	while(!q.empty()){
//		BFSNode u=q.front();q.pop();
//		for(int i=0;i<CharMax;i++)if(trie[u.data].ch[i])q.push(BFSNode{trie[u.data].ch[i],u.data,(char)i});
//		int t=trie[u.pre].failch;
//		while(t&&!trie[t].ch[(int)u.ch])t=trie[t].failch;
//		if(t)trie[u.data].failch=trie[t].ch[u.ch];
//		else trie[u.data].failch=0;
//	}
	queue<int>q;
	q.push(0);
	trie[0].failch=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<CharMax;i++){
			if(!trie[u].ch[i])continue;
			q.push(trie[u].ch[i]);
			int t=trie[u].failch;
			while(t&&(!trie[t].ch[i]))t=trie[t].failch;
			if(t)trie[trie[u].ch[i]].failch=trie[t].ch[i];
			else trie[trie[u].ch[i]].failch=0;
		}
	}
}
int ACauto(string &str){
	int ans=0;int t=0;
	for(int i=0;i<(int)str.length();i++){
		while(t&&!trie[t].ch[(int)str[i]])t=trie[t].failch;
		if(t)t=trie[t].ch[(int)str[i]];
		else t=0;
		for(int j=t;j;j=trie[j].failch){
			ans+=trie[j].count;
			trie[j].count=0;
		}
	}
	return(ans);
}
int n;
string s;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		Insert(s);
	}
	cin>>s;
	FailBFS();
	cout<<ACauto(s);
	return(0);
}
2022/1/26 16:21
加载中...