【模板】AC自动机
简单版
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define rg register int #define I inline int #define V inline void #define ll long long #define db double #define B inline bool #define F1(i,a,b) for(rg i=a;i<=b;++i) #define F2(i,a,b) for(rg i=a;i>=b;--i) #define ed putchar('\n') #define bl putchar(' ') #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) //#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) //char buf[1<<21],*p1=buf,*p2=buf; const int N=1000005; template<typename TP>V read(TP &x) { TP f=1;x=0;register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); x*=f; } template<typename TP>V print(TP x) { if(x<0) x=-x,putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); } int n,trie[N][26],fail[N],tot,end[N]; char s[N]; struct T{ V insert(char s[]) { rg rt=0; for(rg i=1;s[i];++i) { rg id=s[i]-'a'; if(!trie[rt][id]) trie[rt][id]=++tot; rt=trie[rt][id]; } ++end[rt]; } V build() { queue<int>q; memset(fail,0,sizeof fail); F1(i,0,25) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()) { rg x=q.front();q.pop(); F1(i,0,25) { if(trie[x][i]) { fail[trie[x][i]]=trie[fail[x]][i]; q.push(trie[x][i]); } else trie[x][i]=trie[fail[x]][i]; } } } I query(char t[]) { rg rt=0,res=0; for(rg i=1;t[i];++i) { rt=trie[rt][t[i]-'a']; for(rg k=rt;k&&(~end[k]);k=fail[k]) res+=end[k],end[k]=-1; } return res; } }ac; int main() { // freopen("testdata.in","r",stdin); read(n); F1(i,1,n) { scanf("%s",s+1); ac.insert(s); } ac.build(); scanf("%s",s+1),print(ac.query(s)); return 0; }
------------------------------------------------------------------------------------------------
加强版（暴力版）
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define rg register int #define I inline int #define V inline void #define ll long long #define db double #define B inline bool #define F1(i,a,b) for(rg i=a;i<=b;++i) #define F2(i,a,b) for(rg i=a;i>=b;--i) #define ed putchar('\n') #define bl putchar(' ') #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) template<typename TP>V read(TP &x) { TP f=1;x=0;register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); x*=f; } template<typename TP>V print(TP x) { if(x<0) x=-x,putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); } const int N=1000005; int n,trie[N][26],fail[N],tot,end[N],count[N]; struct A{ int num[72],cnt; }ans[20005]; char s[152][72],t[N]; V init() { tot=0; memset(end,0,sizeof end); memset(fail,0,sizeof fail); memset(trie,0,sizeof trie); memset(ans,0,sizeof ans); memset(count,0,sizeof count); } struct T{ V insert(char s[],rg Num) { rg rt=0; for(rg i=0;s[i];++i) { rg id=s[i]-'a'; if(!trie[rt][id]) trie[rt][id]=++tot; rt=trie[rt][id]; } ++end[rt],ans[rt].num[++ans[rt].cnt]=Num; } V build() { queue<int>q; memset(fail,0,sizeof fail); F1(i,0,25) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()) { rg x=q.front();q.pop(); F1(i,0,25) { if(trie[x][i]) { fail[trie[x][i]]=trie[fail[x]][i]; q.push(trie[x][i]); } else trie[x][i]=trie[fail[x]][i]; } } } V query(char t[]) { rg rt=0; for(rg i=0;t[i];++i) { rt=trie[rt][t[i]-'a']; for(rg k=rt;k;k=fail[k]) // { // end[k]=-1; F1(j,1,ans[k].cnt) ++count[ans[k].num[j]]; // } } } }ac; int main() { while(~scanf("%d",&n)&&n) { init(); F1(i,1,n) { scanf("%s",s[i]); ac.insert(s[i],i); } scanf("%s",t),ac.build(); ac.query(t); rg maxx=0; F1(i,1,n) maxx=Max(maxx,count[i]); print(maxx),ed; // F1(i,1,n) printf("%d ",count[i]); F1(i,1,n) if(count[i]==maxx) printf("%s\n",s[i]); } return 0; }
------------------------------------------------------------------------------------------------
加强版（std）
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define rg register int #define I inline int #define V inline void #define ll long long #define db double #define B inline bool #define F1(i,a,b) for(rg i=a;i<=b;++i) #define F2(i,a,b) for(rg i=a;i>=b;--i) #define ed putchar('\n') #define bl putchar(' ') #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) template<typename TP>V read(TP &x) { TP f=1;x=0;register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); x*=f; } template<typename TP>V print(TP x) { if(x<0) x=-x,putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); } const int N=1000005; const int M=155*75; char s[155][75],t[N]; int n; struct AC_Automaton{ int tot,fail[M],trie[M][26],count[M],end[M],last[M]; V init() { tot=0; memset(fail,0,sizeof fail); memset(trie,0,sizeof trie); memset(count,0,sizeof count); memset(last,0,sizeof last); memset(end,0,sizeof end); } V insert(char s[],rg Num) { rg rt=0; for(rg i=0;s[i];++i) { rg id=s[i]-'a'; if(!trie[rt][id]) trie[rt][id]=++tot; rt=trie[rt][id]; } end[rt]=Num; } V build() { queue<int>q; F1(i,0,25) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()) { rg x=q.front(),fx=fail[x]; q.pop(); F1(i,0,25) { rg v=trie[x][i]; if(v) { fail[v]=trie[fx][i]; if(end[fail[v]]) last[v]=fail[v]; else last[v]=last[fail[v]]; q.push(v); } else trie[x][i]=trie[fx][i]; // if(trie[x][i]) // { // fail[trie[x][i]]=trie[fail[x]][i]; // q.push(trie[x][i]); // } // else trie[x][i]=trie[fail[x]][i]; // last[trie[x][i]]=end[fail[trie[x][i]]]?fail[trie[x][i]]:last[fail[trie[x][i]]]; } } } V query(char t[]) { rg rt=0,ans=0; for(rg i=0;t[i];++i) { rt=trie[rt][t[i]-'a']; if(end[rt]) ++count[end[rt]]; rg v=last[rt]; while(v) { if(end[v]) ++count[end[v]]; v=last[v]; } } F1(i,1,n) ans=Max(ans,count[i]); print(ans),ed; F1(i,1,n) if(count[i]==ans) printf("%s\n",s[i]); } }ac; int main() { // freopen("testdata(1).in","r",stdin); while(~scanf("%d",&n)&&n) { ac.init(); F1(i,1,n) { scanf("%s",s[i]); ac.insert(s[i],i); } ac.build(); scanf("%s",t),ac.query(t); } return 0; }
