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;
}