同3942，建出AC自动机以后直接用栈来加入，只要在fail树上匹配成功就弹出。 复习一波AC自动机。。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; int fail[N],top,tot,q[N],ch[N][27],dep[N]; char s1[N],s[N]; int n,a[N]; char st[N]; inline int newnode() { tot++; fo(i,0,25)ch[tot][i]=-1; return tot; } inline void ins() { int n=strlen(s1+1),x=1; fo(i,1,n) { if (ch[x][s1[i]-'a']==-1)ch[x][s1[i]-'a']=newnode(); x=ch[x][s1[i]-'a']; } dep[x]=n; } inline void AC_mach() { int t=0,w=0; fail[1]=1; fo(i,0,25) if (ch[1][i]==-1)ch[1][i]=1; else{ fail[ch[1][i]]=1; q[++w]=ch[1][i]; } while (t<w) { int x=q[++t]; fo(i,0,25) if (ch[x][i]==-1)ch[x][i]=ch[fail[x]][i]; else { fail[ch[x][i]]=ch[fail[x]][i]; q[++w]=ch[x][i]; } } } int main() { scanf("%s",s+1); scanf("%d",&n); tot=0; newnode(); fo(i,1,n)scanf("%s",s1+1),ins(); AC_mach(); int x=1,len=strlen(s+1); a[0]=1; fo(i,1,len) { st[++top]=s[i]; x=ch[x][s[i]-'a']; a[top]=x; if (dep[x])top-=dep[x],x=a[top]; } fo(i,1,top)printf("%c",st[i]); printf("\n"); return 0; }