HDU-2896 病毒侵袭（AC自动机）

题意：求模式串在文本串中是否出现，出现则输出其编号；
思路：AC自动机模板题，结尾处标识字符串的ID即可；
注意：ASCII 码，数组需要开到130；
  1 /*
  2 * @Author: windystreet
  3 * @Date:   2018-07-26 09:22:19
  4 * @Last Modified by:   windystreet
  5 * @Last Modified time: 2018-07-27 18:58:12
  6 */
  7 #include<bits/stdc++.h>
  8 
  9 using namespace std;
 10 
 11 #define X first
 12 #define Y second
 13 #define eps  1e-2
 14 #define gcd __gcd
 15 #define pb push_back
 16 #define PI acos(-1.0)
 17 #define lowbit(x) (x)&(-x)
 18 #define bug printf("!!!!!
");
 19 #define mem(x,y) memset(x,y,sizeof(x))
 20 
 21 typedef long long LL;
 22 typedef long double LD;
 23 typedef pair<int,int> pii;
 24 typedef unsigned long long uLL;
 25 
 26 const int maxn = 1e5+7;
 27 const LL  INF  = 1<<30;
 28 const int mod  = 1e9+7;
 29 
 30 int ch[maxn][130];
 31 int last[maxn],sz=1,flag;
 32 int f[maxn];
 33 int val[maxn];
 34 set<int>ans;
 35 void init(){
 36     sz = 1;
 37     mem(ch[0],0);
 38     mem(last,0);
 39 }
 40 
 41 
 42 int idx(char a){return int(a);}
 43 
 44 void insert(char *s,int id){
 45     int len = strlen(s),cur = 0;
 46     for(int i = 0; i < len; i++){
 47         int c = idx(s[i]);
 48         if(!ch[cur][c]){
 49             mem(ch[sz],0);
 50             ch[cur][c] = sz++;
 51         }
 52         cur = ch[cur][c];
 53     }
 54      val[cur] = id;  //记录ID
 55 }
 56 void print(int i,int j){
 57     if(j){
 58         ans.insert(val[j]);   //找到了答案就放入set中，自动排序
 59         print(i,last[j]);
 60     }
 61 }
 62 void getfail(){
 63     queue<int>q;
 64     f[0] = 0;
 65     int u ;
 66     for(int i=0;i<130;i++){
 67         u = ch[0][i];
 68         if(u){
 69             f[u] = 0;
 70             q.push(u);
 71             last[u] = 0;
 72         }
 73     }
 74     while(!q.empty()){
 75         int cur = q.front();q.pop();
 76         for(int i=0;i<130;i++){
 77             u = ch[cur][i];
 78             if(!u){ch[cur][i] = ch[f[cur]][i]; continue;}
 79             q.push(u);
 80         
 81         int tmp = f[cur];
 82         if(tmp && !ch[tmp][i]) tmp = ch[f[tmp]][i];
 83         f[u] = ch[tmp][i];
 84         last[u] = val[f[u]] ? f[u] : last[f[u]];
 85         }
 86 
 87     }
 88 }
 89 int find(char *s){
 90     int len = strlen(s), u = 0;
 91     for(int i=0;i<len;i++){
 92         int c = idx(s[i]);
 93         u = ch[u][c];
 94         if(val[u]) print(i,u);
 95         else if(last[u]) print(i,last[u]);
 96     }
 97     return flag;
 98 }
 99 char s[maxn];
100 void solve(){
101     int n,m,cnt= 0;
102     while(scanf("%d",&n)!=EOF){
103         cnt = 0;
104         init();
105         scanf("%d",&n);
106         for (int i = 0; i < n; ++i)
107         {
108             scanf("%s",s);
109             insert(s,i+1);  //插入其ID；
110         }
111         getfail();
112         scanf("%d",&m);
113         for(int i=1;i<=m;i++){
114             ans.clear();
115             scanf("%s",s);
116             find(s);
117             if(ans.size()){
118                 cnt++;
119                 printf("web %d:",i);
120                 for(auto it :ans){
121                     printf(" %d",it);
122                 }puts("");
123             }
124 
125         }
126         printf("total: %d
",cnt);
127     }
128     return;
129 }
130 
131 int main()
132 {
133 //    freopen("in.txt","r",stdin);
134 //    freopen("out.txt","w",stdout);
135 //    ios::sync_with_stdio(false);
136     int t = 1;
137     //scanf("%d",&t);
138     while(t--){
139     //    printf("Case %d: ",cas++);
140         solve();
141     }
142     return 0;
143 }
HDU-2896 病毒侵袭 （AC自动机）

HDU-2896 病毒侵袭（AC自动机）
