AC自动机解题记录

1.HDU 2222 Keywords Search 

模板题

 1 #include <bits/stdc++.h>
 2 #define fir first
 3 #define sec second
 4 #define EPS 1e-12
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 typedef pair<int , int > pii;
 9 const int MAXN=5e5+5;
10 
11 struct Trie{
12     int nxt[MAXN][26],fail[MAXN],ed[MAXN];
13     int root,L;
14     int newnode(){
15         for(int i=0;i<26;i++)
16             nxt[L][i]=-1;
17         ed[L++]=0;
18         return L-1;
19     }
20     void init(){
21         L=0;
22         root=newnode();
23     }
24     void Insert(char buf[]){
25         int len=strlen(buf);
26         int now=root;
27         for(int i=0;i<len;++i){
28             if(nxt[now][buf[i]-'a']==-1)
29                 nxt[now][buf[i]-'a']=newnode();
30             now=nxt[now][buf[i]-'a'];
31         }
32         ed[now]++;
33     }
34     void build(){
35         queue <int > Q;
36         fail[root]=root;
37         for(int i=0;i<26;++i)
38             if(nxt[root][i]==-1)
39                 nxt[root][i]=root;
40             else{
41                 fail[nxt[root][i]]=root;
42                 Q.push(nxt[root][i]);
43             }
44         while(!Q.empty()){
45             int now=Q.front();Q.pop();
46             for(int i=0;i<26;++i)
47                 if(nxt[now][i]==-1)
48                     nxt[now][i]=nxt[fail[now]][i];
49                 else{
50                     fail[nxt[now][i]]=nxt[fail[now]][i];
51                     Q.push(nxt[now][i]);
52                 }
53         }
54     }
55     int query(char buf[]){
56         int len=strlen(buf);
57         int now=root;
58         int res=0;
59         for(int i=0;i<len;++i){
60             now=nxt[now][buf[i]-'a'];
61             int temp=now;
62             while(temp!=root){
63                 res+=ed[temp];
64                 ed[temp]=0;
65                 temp=fail[temp];
66             }
67         }
68         return res;
69     }
70 };
71 Trie ac;
72 char buf[1000006];
73 int main()
74 {
75     int Test;
76     int N;
77     scanf("%d",&Test);
78     while(Test--){
79         scanf("%d",&N);
80         ac.init();
81         for(int i=0;i<N;++i)
82         {
83             scanf("%s",buf);
84             ac.Insert(buf);
85         }
86         ac.build();
87         scanf("%s",buf);
88         printf("%d
",ac.query(buf));
89     }
90     return 0;
91 }
View Code

2.HDU 2896 病毒侵袭

给模式串分配id

  1 #include <bits/stdc++.h>
  2 #define fir first
  3 #define sec second
  4 #define EPS 1e-12
  5 using namespace std;
  6 
  7 typedef long long LL;
  8 typedef pair<int , int > pii;
  9 const int MAXN=500*200+5;
 10 
 11 struct Trie{
 12     int nxt[MAXN][128],fail[MAXN],ed[MAXN];
 13     int root,L;
 14     int newnode(){
 15         for(int i=0;i<128;i++)
 16             nxt[L][i]=-1;
 17         ed[L++]=-1;
 18         return L-1;
 19     }
 20     void init(){
 21         L=0;
 22         root=newnode();
 23     }
 24     void Insert(char buf[],int id){
 25         int len=strlen(buf);
 26         int now=root;
 27         for(int i=0;i<len;++i){
 28             if(nxt[now][buf[i]-0]==-1)
 29                 nxt[now][buf[i]-0]=newnode();
 30             now=nxt[now][buf[i]-0];
 31         }
 32         ed[now]=id;
 33     }
 34     void build(){
 35         queue <int > Q;
 36         fail[root]=root;
 37         for(int i=0;i<128;++i)
 38             if(nxt[root][i]==-1)
 39                 nxt[root][i]=root;
 40             else{
 41                 fail[nxt[root][i]]=root;
 42                 Q.push(nxt[root][i]);
 43             }
 44         while(!Q.empty()){
 45             int now=Q.front();Q.pop();
 46             for(int i=0;i<128;++i)
 47                 if(nxt[now][i]==-1)
 48                     nxt[now][i]=nxt[fail[now]][i];
 49                 else{
 50                     fail[nxt[now][i]]=nxt[fail[now]][i];
 51                     Q.push(nxt[now][i]);
 52                 }
 53         }
 54     }
 55     bool vis[512];
 56     bool query(char buf[],int id,int N){
 57         int len=strlen(buf);
 58         int now=root;
 59         bool flag=false;
 60         memset(vis,false,sizeof(vis));
 61         for(int i=0;i<len;++i){
 62             now=nxt[now][buf[i]-0];
 63             int temp=now;
 64             while(temp!=root){
 65                 if(ed[temp]!=-1){
 66                     vis[ed[temp]]=true;
 67                     flag=true;
 68                 }
 69                 temp=fail[temp];
 70             }
 71         }
 72         if(!flag) return false;
 73         printf("web %d:",id);
 74         for(int i=1;i<=N;++i)
 75             if(vis[i]) printf(" %d",i);
 76         puts("");
 77         return true;
 78     }
 79 };
 80 Trie ac;
 81 char buf[10000+4];
 82 int main()
 83 {
 84     int N,M;
 85     scanf("%d",&N);
 86     ac.init();
 87     for(int i=1;i<=N;++i)
 88     {
 89         scanf("%s",buf);
 90         ac.Insert(buf,i);
 91     }
 92     ac.build();
 93     scanf("%d",&M);
 94     int tot=0;
 95     for(int i=1;i<=M;++i){
 96         scanf("%s",buf);
 97         if(ac.query(buf,i,N)) tot++;
 98     }
 99     printf("total: %d
",tot);
100     return 0;
101 }
View Code

3.HDU 3065 病毒侵袭持续中

给模式串分配id 并记录出现次数

 1 #include <bits/stdc++.h>
 2 #define fir first
 3 #define sec second
 4 #define EPS 1e-12
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 typedef pair<int , int > pii;
 9 const int MAXN=1000*55+5;
10 
11 int res[1000+3];
12 char virus[1000+3][60];
13 
14 struct Trie{
15     int nxt[MAXN][128],fail[MAXN],ed[MAXN],ed1[MAXN];//ed 存编号 ed1存个数
16     int root,L;
17     int newnode(){
18         for(int i=0;i<128;i++)
19             nxt[L][i]=-1;
20         ed[L]=-1;
21         ed1[L++]=0;
22         return L-1;
23     }
24     void init(){
25         L=0;
26         root=newnode();
27     }
28     void Insert(char buf[],int id){
29         int len=strlen(buf);
30         int now=root;
31         for(int i=0;i<len;++i){
32             if(nxt[now][buf[i]-0]==-1)
33                 nxt[now][buf[i]-0]=newnode();
34             now=nxt[now][buf[i]-0];
35         }
36         ed[now]=id;
37         ed1[now]++;
38     }
39     void build(){
40         queue <int > Q;
41         fail[root]=root;
42         for(int i=0;i<128;++i)
43             if(nxt[root][i]==-1)
44                 nxt[root][i]=root;
45             else{
46                 fail[nxt[root][i]]=root;
47                 Q.push(nxt[root][i]);
48             }
49         while(!Q.empty()){
50             int now=Q.front();Q.pop();
51             for(int i=0;i<128;++i)
52                 if(nxt[now][i]==-1)
53                     nxt[now][i]=nxt[fail[now]][i];
54                 else{
55                     fail[nxt[now][i]]=nxt[fail[now]][i];
56                     Q.push(nxt[now][i]);
57                 }
58         }
59     }
60     void query(char buf[],int N){
61         for(int i=1;i<=N;++i) res[i]=0;
62         int len=strlen(buf);
63         int now=root;
64         for(int i=0;i<len;++i){
65             now=nxt[now][buf[i]-0];
66             int temp=now;
67             while(temp!=root){
68                 if(ed[temp]!=-1){
69                     res[ed[temp]]++;
70                 }
71                 temp=fail[temp];
72             }
73         }
74         for(int i=1;i<=N;++i)
75             if(res[i]) printf("%s: %d
",virus[i],res[i]);
76     }
77 };
78 Trie ac;
79 char buf[2000000+6];
80 int main()
81 {
82     int N;
83     while(~scanf("%d",&N)){
84     ac.init();
85     for(int i=1;i<=N;++i)
86     {
87         scanf("%s",virus[i]);
88         ac.Insert(virus[i],i);
89     }
90     ac.build();
91     scanf("%s",buf);
92 
93     ac.query(buf,N);
94     }
95     return 0;
96 }
View Code

4.Gym - 101741K Consistent Occurrences

离线AC自动机，把所有询问的模式串建立自动机用id标记不同的询问，然后查询时有点麻烦地从左到右记录出现的不相交子串，开个数组记答案，还要开个数组记位置。
最让人没想到的是还会出现相同的询问，所以要处理相同模式串的id，以免出现后出现的询问覆盖前出现。

  1 #include <bits/stdc++.h>
  2 #define fir first
  3 #define sec second
  4 #define EPS 1e-12
  5 using namespace std;
  6 
  7 typedef long long LL;
  8 typedef pair<int , int > pii;
  9 const int MAXN=2e5+5;
 10 
 11 int res[100000+5];
 12 int evelen[100000+5];
 13 int loc[100000+5];
 14 int strid[100000+5];
 15 
 16 struct Trie{
 17     int nxt[MAXN][26],fail[MAXN],ed[MAXN],ed1[MAXN];//ed 存编号 ed1存个数
 18     int root,L;
 19     int newnode(){
 20         for(int i=0;i<26;i++)
 21             nxt[L][i]=-1;
 22         ed[L]=-1;
 23         ed1[L++]=0;
 24         return L-1;
 25     }
 26     void init(){
 27         L=0;
 28         root=newnode();
 29     }
 30     void Insert(string buf,int id){
 31         int len=buf.size();
 32         int now=root;
 33         for(int i=0;i<len;++i){
 34             if(nxt[now][buf[i]-'a']==-1)
 35                 nxt[now][buf[i]-'a']=newnode();
 36             now=nxt[now][buf[i]-'a'];
 37         }
 38         ed[now]=id;
 39         ed1[now]++;
 40     }
 41     void build(){
 42         queue <int > Q;
 43         fail[root]=root;
 44         for(int i=0;i<26;++i)
 45             if(nxt[root][i]==-1)
 46                 nxt[root][i]=root;
 47             else{
 48                 fail[nxt[root][i]]=root;
 49                 Q.push(nxt[root][i]);
 50             }
 51         while(!Q.empty()){
 52             int now=Q.front();Q.pop();
 53             for(int i=0;i<26;++i)
 54                 if(nxt[now][i]==-1)
 55                     nxt[now][i]=nxt[fail[now]][i];
 56                 else{
 57                     fail[nxt[now][i]]=nxt[fail[now]][i];
 58                     Q.push(nxt[now][i]);
 59                 }
 60         }
 61     }
 62     void query(string buf,int N){
 63         for(int i=1;i<=N;++i) { res[i]=0; loc[i]=-1;}
 64         int len=buf.size();
 65         int now=root;
 66         for(int i=0;i<len;++i){
 67             now=nxt[now][buf[i]-'a'];
 68             int temp=now;
 69             while(temp!=root){
 70                 if(ed[temp]!=-1){
 71                     int _id=ed[temp];
 72                     if(i>=loc[_id]+evelen[_id]){
 73                         res[_id]++;
 74                         //printf("loc[%d] = %d
",_id,loc[_id]);
 75                         loc[_id]=i;
 76                         //printf("%d: loc[%d] = %d
",i,_id,loc[_id]);
 77                     }
 78                 }
 79                 temp=fail[temp];
 80             }
 81         }
 82         for(int i=1;i<=N;++i)
 83             printf("%d
",res[strid[i]]);
 84     }
 85 };
 86 Trie ac;
 87 string buf;
 88 string ob;
 89 map<string ,int > mp;
 90 int main()
 91 {
 92     ios::sync_with_stdio(false);
 93     int N,M;
 94     cin>>N>>M;
 95     cin>>ob;
 96     ac.init();
 97     for(int i=1;i<=M;++i)
 98     {
 99         cin>>buf;
100         if(mp.count(buf)) strid[i]=mp[buf];
101         else{
102             mp[buf]=i;
103             strid[i]=i;
104         }
105         evelen[strid[i]]=buf.size();
106         ac.Insert(buf,strid[i]);
107     }
108     ac.build();
109     ac.query(ob,M);
110     return 0;
111 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Kiritsugu/p/9350965.html