HDU 2896 病毒侵袭 (AC自动机)

原题网址：

http://acm.hdu.edu.cn/showproblem.php?pid=2896

题意：

因为是中文题，我就不翻译成英语了。。。

思路：

ac自动机的模板题。

博主不想说话并扔了一串代码给你。

#include <bits/stdc++.h>
using namespace std;

#define maxnode 100001
#define sigma 128

struct ac_automation{
int ch[maxnode][sigma];
// maxnode 一般设置为 模式串数量*模式串长度
//ch数组里存的都是位置信息，甚至包含了一些失效指针的信息。
int val[maxnode];
//int cnt[maxnode]; // count
int last[maxnode]; // 储存着最后在查询时需要向上层回溯的地址。
int f[maxnode]; // fail指针
int sz;  // the num of the trie
int ans; // answer
int num = 0;
int w[3];

void clear(){ 
        sz = 1;
        ans = 0;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
//memset(cnt,0,sizeof(cnt));
    }
int idx(char c){
return (int)c;
    }

void insert(char s[],int v){ 
int u = 0;
for(int i = 0; s[i];i++){
int c = idx( s[i] );
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
//cnt[u]++;
        val[u] = v;  
    }

void build(){
        f[0] = 0;
queue<int> q;
for(int i = 0;i < sigma;i++){
if(ch[0][i]){
                f[ch[0][i]] = 0; 
                q.push(ch[0][i]);
                last[ch[0][i]] = 0;
            }
        }

while(!q.empty()){
int now = q.front();
            q.pop();
for(int i = 0;i < sigma ;i++){
int son = ch[now][i];
if(!son){
                    ch[now][i] = ch[f[now]][i];
continue;
                }
                q.push(son);
                f[son] = ch[f[now]][i];
                last[son] = val[f[son]] ? f[son] : last[f[son]];
            }
        }
    }

void find(char *s){
int u = 0;
for(int i = 0;s[i];i++){
if(num == 3){
return;
            }
int c = idx(s[i]);
            u = ch[u][c];
if(val[u]){
                print(u);
            }
else{
                print(last[u]);
            }
        }
    }
void print(int u){
if(u){
//if(val[u])
            w[num++] = val[u];
//ans += cnt[u];
//cnt[u] = 0;
            print(last[u]);
        }
    }

}ac;


char sub[210];
char web[10010];


int main()
{
int n;
cin>>n;
    ac.clear();
for(int i = 1;i <= n;i++){
scanf("%s",sub);
        ac.insert(sub,i);
    }
    ac.build();
cin>>n;
int total = 0;
for(int i = 1;i <= n;i++){
scanf("%s",web);
        ac.find(web);
if(ac.num != 0){
            total += 1;
printf("web %d:",i);
            sort(ac.w,ac.w + ac.num);
for(int j = 0;j < ac.num;j++){
printf(" %d",ac.w[j]);
            }
printf("\n");
            ac.num = 0;
        }
    }
printf("total: %d\n",total);

return 0;
}