这是一个板子页面
比他们慢了快一年，终于开始学AC自动机了。。
不知道为什么他们博客里都各种试水试水的搞得我好尴尬
话说老外的板子真好看
敲完这道题也就大概知道自动机的原理以及自动在哪里。。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=5e5;
const int M=1e6+5;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
char str[M];
struct trie{
struct node{
int to[26],g,d;
}tr[M];
int allc,que[N];
inline void clear(){
for(int i=1;i<=allc;++i){
for(int j=0;j<26;++j)
tr[i].to[j]=0;
tr[i].d=0;
}
allc=1;
}
inline void Insert(int len){
int rt=1;
for(int i=0;i<len;++i){
if(!tr[rt].to[str[i]])
tr[rt].to[str[i]]=++allc;
rt=tr[rt].to[str[i]];
}
tr[rt].d+=1;
}
inline void build(){
int l=0,r=0;
for(que[r++]=1;l<r;){
int v=que[l++];
for(int i=0;i<26;++i){
int j,s;
for(j=tr[v].g;j;j=tr[j].g)
if(tr[j].to[i])break;
//沿着祖宗们的失配函数跳啊跳，调到祖宗的失配函数也可以包含自己为止
if(s=tr[v].to[i]){
tr[s].g=j?tr[j].to[i]:1;
// tr[s].d+=tr[tr[s].g].d;
que[r++]=s;
}
else tr[v].to[i]=j?tr[j].to[i]:1;//补上一条边方便匹配
}
}
}
}ac;
inline void gao(){
int n;cin>>n;
ac.clear();
for(int i=1;i<=n;++i){
scanf("%s",str);
int l=strlen(str);
for(int j=0;j<l;++j)
str[j]-='a';
ac.Insert(l);
}
ac.build();
scanf("%s",str);
int m=strlen(str),res=0,rt=1;
for(int i=0,j;i<m;++i){
str[i]-='a';
rt=ac.tr[rt].to[str[i]];
if(ac.tr[rt].d){
for(j=rt;;j=ac.tr[j].g){
res+=ac.tr[j].d;
ac.tr[j].d=0;
if(j==1)break;
}
}
}
printf("%d\n",res);
}
int main(){
int _;
for(cin>>_;_--;)gao();
return 0;
}
这道题生动的讲解了自动机的复杂度堆在哪
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int M=50005;
#define debug(x) cout<<#x<<"="<<x<<endl
int n,allc;
struct node{
int to[26],g,d;
}tr[M];
char P[1005][55],str[2000005];
int cnt[1005],que[M];
inline void clear(){
for(int i=1;i<=allc;++i)
for(int j=tr[i].g=tr[i].d=0;j<26;++j)
tr[i].to[j]=0;
allc=1;
}
inline void Insert(int id,int len){
int rt=1;
for(int i=0;i<len;++i){
if(!tr[rt].to[P[id][i]])
tr[rt].to[P[id][i]]=++allc;
rt=tr[rt].to[P[id][i]];
}
tr[rt].d=id;
}
inline void build(){
int l=0,r=0;
for(que[r++]=1;l<r;){
int u=que[l++];
for(int i=0,j,s;i<26;++i){
for(j=tr[u].g;j;j=tr[j].g)
if(tr[j].to[i])break;
if(s=tr[u].to[i]){
tr[s].g=j?tr[j].to[i]:1;
que[r++]=s;
}
else tr[u].to[i]=j?tr[j].to[i]:1;
}
}
}
inline bool check(char &s){
return s>='A'&&s<='Z';
}
inline void gao(){
clear();
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;++i){
scanf("%s",P[i]);
int l=strlen(P[i]);
for(int j=0;j<l;++j)
P[i][j]-='A';
Insert(i,l);
for(int j=0;j<l;++j)
P[i][j]+='A';
}
build();
scanf("%s",str);
int m=strlen(str),rt=1;
for(int i=0;i<m;++i){
if(!check(str[i])){rt=1;continue;}
int c=str[i]-'A';
rt=tr[rt].to[c];
for(int j=rt;;j=tr[j].g){
++cnt[tr[j].d];
if(j==1)break;
}
}
for(int i=1;i<=n;++i)
if(cnt[i])
printf("%s: %d\n",P[i],cnt[i]);
}
int main(){
for(;cin>>n;)gao();
return 0;
}