求助AC自动机
查看原帖
求助AC自动机
241260
123456Mm楼主2021/5/17 19:10

RT AC自动机板子求调,谢谢

第1个点 TLE 疑似死循环

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=1e6+10;
int n;
string s;
string t;
int ch[MAXN][30],bo[MAXN],nxt[MAXN];
int tot=1;
void insert(){
	int len=s.length();
	int u=1;
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		if(!ch[u][c]){
			tot++;
			ch[u][c]=tot;
		}
		u=ch[u][c];
	}
	bo[u]++;
	return;
}
void BFS(){
	queue<int> q;
	q.push(1);
	for(int i=0;i<=25;i++)ch[0][i]=1;
	nxt[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<=25;i++){
			if(!ch[u][i])ch[u][i]=ch[nxt[u]][i];
			else {
				q.push(ch[u][i]);
				int v=nxt[u];
				nxt[ch[u][i]]=ch[v][i];
			}
		}
	}
}
int ans=0;
void find(){
	int len=t.length();
	int u=1;
	for(int i=0;i<len;i++){
		int c=t[i]-'a';
		int k=ch[u][c];
		while(k>1){
			ans+=bo[k];
			bo[k]=0;
			k=nxt[k];
		}
		u=ch[u][c];
	}
	return;
}
int main(){
	//freopen("AC.in","r",stdin);
	cin>>n;
	//cout<<"YEAH"<<endl;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert();
	}
	//cout<<"YEAH"<<endl;
	BFS();
	//cout<<"YEAH"<<endl;
	cin>>t;
	find();
	cout<<ans<<endl;
}
2021/5/17 19:10
加载中...