手搓AC自动机,全RE求调
查看原帖
手搓AC自动机,全RE求调
499140
3wykx楼主2023/11/4 15:52

RE了,也许是犯了某种低级错误?

#include <bits/stdc++.h>
using namespace std;
int n,ans,len,tot=1;  //ans为最终答案,tot为字典树的节点数 
char s[1000005];
char ch[1000005][27];
int num[1000005],fail[1000005];  //num为标记数组,ch为trie,s为输入数组 
void insert() {  //构建trie
	int u=1;
	len=strlen(s);
	for(int i=0; i<len; i++) {
		int v=s[i]-'a';
		if(!ch[u][v])ch[u][v]=++tot;
		u=ch[u][v];
	}
	num[u]++;
}
void Make_Fail() {  //bfs求fail数组 
	for(int i=0; i<26; i++)ch[0][i]=1;
	queue<int> q;
	q.push(1);
	fail[1]=0;
	while(!q.empty()) {
		int nw=q.front();
		q.pop();
		for(int i=0; i<26; i++) {
			int son=ch[nw][i],fafail=fail[nw];  //son为当前儿子,fafail为son的父亲的fail 
			if(!son) {
				ch[nw][i]=ch[fafail][i];
				continue;
			}
			fail[son]=ch[fafail][i];
			q.push(son);
		}
	}
}
void Aho_Corasick_Automaton() {  //AC自动机匹配部分 
	int u=1;
	len=strlen(s);
	for(int i=0; i<len; i++) {
		int v=s[i]-'a';
		int son=ch[u][v];
		while(son>1&&num[son]!=-1) {
			ans+=num[son];
			num[son]=-1;
			son=fail[son];
		}
		u=ch[u][v];
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		cin>>s;
		insert();
	}
	Make_Fail();
	cin>>s;
	Aho_Corasick_Automaton();
	cout<<ans<<endl;
	return 0;
}
2023/11/4 15:52
加载中...