1 /*  2 hdu 2896 病毒侵袭 ac自动机   3 从题意得知，模式串中没有重复的串出现，所以结构体中可以将last[]（后缀链接）数组去掉   4 last[]数组主要是记录具有相同后缀模式串的末尾节点编号 。本题中主要是计算每一个模式串  5 在主串中有没有出现过，而不是计算出现过多少次，所以将last[]数组省掉....   6 */   7 #include<algorithm>  8 #include<iostream>  9 #include<cstdio> 10 #include<cstring> 11 #include<queue>  12 #define N 210*500 13 using namespace std; 14 class AC_atomata 15 { 16 public: 17    int trie[N][128],  f[N], val[N]; 18    int vis[510]; 19    int nodeN; 20    int total; 21    queue<int>q; 22    void init() 23    { 24       nodeN=0; 25       val[0]=0; 26       total=0; 27       while(!q.empty()) q.pop(); 28       memset(trie[0], 0, sizeof(trie[0])); 29    } 30    void build(char *str, int index);//建立trie树  31    void getFail();//失配函数  32    void find(char *T, int n, int index);//查找函数  33 }; 34  35  36 void AC_atomata::build(char *str, int index) 37 { 38     int i, u; 39     for(i=0, u=0; str[i]; ++i) 40     { 41         int ch=str[i]; 42         if(!trie[u][ch]) 43         { 44             trie[u][ch]=++nodeN; 45             memset(trie[nodeN], 0, sizeof(trie[nodeN])); 46     } 47     u=trie[u][ch]; 48     val[u]=0; 49     } 50     val[u]=index; 51 } 52  53 void AC_atomata::getFail() 54 { 55    int r, u, v, i; 56    f[0]=0; 57    for(i=0; i<128; ++i) 58    { 59        if(trie[0][i]) 60        { 61              q.push(trie[0][i]); 62              f[trie[0][i]]=0; 63        } 64    } 65    while(!q.empty()) 66    { 67       r=q.front(); 68       q.pop(); 69       for(i=0; i<128; ++i) 70       { 71             u=trie[r][i]; 72             if(!u) continue; 73             q.push(u); 74             v=f[r]; 75             while(v && !trie[v][i]) v=trie[v][i]; 76             f[u]=trie[v][i]; 77       } 78    } 79 } 80  81 void AC_atomata::find(char *T, int n, int index) 82 { 83     int i, u; 84     int cnt=0, v[3]; 85     memset(v, 0, sizeof(v)); 86     memset(vis, 0, sizeof(vis));//每一次查找将数组初始化，开始忘记初始化了， 哇了好多次  87     for(i=0, u=0; T[i]; ++i) 88     { 89         int ch=T[i]; 90         while(u && !trie[u][ch])  u=f[u]; 91         u=trie[u][ch]; 92         if(val[u] && !vis[val[u]]) 93         { 94             v[cnt++]=val[u]; 95             vis[val[u]]=1; 96             if(cnt>2) break; 97     } 98     } 99     if(cnt>0)100     {101         ++total;102         printf("web %d:", index);103         sort(v, v+3);104         for(i=0; i<3; ++i)105            if(v[i])  printf(" %d", v[i]);106         printf("\n");107     }108 }109 110 AC_atomata ac;111 char T[10005], s[205];112 113 int main()114 {115    int n, m, i;116    while(scanf("%d", &n)!=EOF)117    {118        ac.init();119        for(i=1; i<=n; ++i)120         {121            scanf("%s", s);122            ac.build(s, i);123     }124        ac.getFail();125        scanf("%d", &m);126        for(i=1; i<=m; ++i)127        {128              scanf("%s", T);129              ac.find(T, n, i);130        }131        printf("total: %d\n", ac.total);132    }133    return 0;134 }