题面

暴力玄学AC自动机

sign记录当前节点扫到AC自动机的哪个地方，我们开一个next数组和pre数组，记录当前这个点的后面那个点是几号、前面那个点是几号，每当发现一个能删去的字符串的时候，暴力跳到字符串头上的pre，将其的next修改为字符串尾的next，修改一下now，继续扫就行，这样也能A。因为要O（n）预处理一下next和pre，所以会比法1稍微慢一丢丢。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=100000+10;
 8 const ll b=131;
 9 ll Hash[maxn],Pow[maxn]={1};
10 char str[maxn],u[maxn],tmp[maxn];
11 struct Tmp
12 {
13     int len;
14     ll Hash;
15 }t[maxn];
16 bool cmp(const Tmp & a,const Tmp & b)
17 {
18     return a.len<b.len;
19 }
20 int ptr;
21 inline ll GetHash(int j,int i)
22 {
23     return Hash[i]-Hash[j-1]*Pow[i-j+1];
24 }
25 int main()
26 {
27     scanf("%s",str+1);
28     int n=strlen(str+1),m;
29     scanf("%d",&m);
30     for(int i=1;i<=m;++i)
31     {
32         scanf("%s",tmp+1);
33         t[i].len=strlen(tmp+1);
34         for(int j=1;j<=t[i].len;++j)
35             t[i].Hash=t[i].Hash*b+tmp[j];
36     }
37     sort(t+1,t+1+m,cmp);
38     for(int i=1;i<=n;++i)
39         Pow[i]=(Pow[i-1]*b);
40     for(int i=1;i<=n;++i)
41     {
42         u[++ptr]=str[i],Hash[ptr]=Hash[ptr-1]*b+u[ptr];
43         while(ptr<t[1].len&&i<n)u[++ptr]=str[++i],Hash[ptr]=Hash[ptr-1]*b+u[ptr];
44         for(int j=1;j<=m&&ptr;++j)
45             if(ptr-t[j].len+1>=1&&GetHash(ptr-t[j].len+1,ptr)==t[j].Hash){ptr-=t[j].len;}
46     }
47     for(int i=1;i<=ptr;++i)
48         putchar(u[i]);
49     puts("");
50     return 0;
51 }