【HDOJ】2896 病毒侵袭

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define TRIEN 128
  8 #define MAXN  505
  9 
 10 typedef struct Trie {
 11     int in;
 12     Trie *fail;
 13     Trie *next[TRIEN];
 14     Trie() {
 15         in = 0;
 16         fail = NULL;
 17         memset(next, 0, sizeof(next));
 18     }
 19 } Trie;
 20 
 21 Trie *root;
 22 char src[205], des[10005];
 23 bool visit[MAXN];
 24 
 25 void create(char str[], int in) {
 26     int i = 0, id;
 27     Trie *p = root, *q;
 28 
 29     while (str[i]) {
 30         id = str[i];
 31         ++i;
 32         if (p->next[id] == NULL) {
 33             q = new Trie();
 34             p->next[id] = q;
 35         }
 36         p = p->next[id];
 37     }
 38     p->in = in;
 39 }
 40 
 41 void build_fail() {
 42     int i;
 43     Trie *p, *q;
 44     queue<Trie *> que;
 45 
 46     for (i=0; i<TRIEN; ++i) {
 47         if (root->next[i]) {
 48             root->next[i]->fail = root;
 49             que.push(root->next[i]);
 50         }
 51     }
 52 
 53     while (!que.empty()) {
 54         p = que.front();
 55         que.pop();
 56         for (i=0; i<TRIEN; ++i) {
 57             if (p->next[i]) {
 58                 q = p->fail;
 59                 while (q != NULL) {
 60                     if (q->next[i]) {
 61                         p->next[i]->fail = q->next[i];
 62                         break;
 63                     }
 64                     q = q->fail;
 65                 }
 66                 if (q == NULL)
 67                     p->next[i]->fail = root;
 68                 que.push(p->next[i]);
 69             }
 70         }
 71     }
 72 }
 73 
 74 void search() {
 75     int i = 0, id;
 76     Trie *p = root, *tmp;
 77 
 78     while (des[i]) {
 79         id = des[i];
 80         ++i;
 81         while (p->next[id]==NULL && p!=root)
 82             p = p->fail;
 83         p = p->next[id];
 84         if (p == NULL)
 85             p = root;
 86         tmp = p;
 87         while (tmp != root) {
 88             visit[tmp->in] = true;
 89             tmp = tmp->fail;
 90         }
 91     }
 92 }
 93 
 94 void del(Trie *t) {
 95     if (t == NULL)
 96         return ;
 97     for (int i=0; i<TRIEN; ++i)
 98         del(t->next[i]);
 99     delete t;
100 }
101 
102 int main() {
103     int n, m, cnt, total;
104     int i;
105 
106     while (scanf("%d",&n) != EOF) {
107         root = new Trie();
108         for (i=1; i<=n; ++i) {
109             scanf("%s", src);
110             create(src, i);
111         }
112         build_fail();
113         scanf("%d", &m);
114         total = 0;
115         for (i=1; i<=m; ++i) {
116             scanf("%s", des);
117             memset(visit, false, sizeof(visit));
118             search();
119             cnt = 0;
120             for (int j=1; j<=n; ++j) {
121                 if (visit[j]) {
122                     if (!cnt)
123                         printf("web %d:", i);
124                     ++cnt;
125                     printf(" %d", j);
126                 }
127             }
128             if (cnt) {
129                 printf("\n");
130                 ++total;
131             }
132         }
133         printf("total: %d\n", total);
134         del(root);
135     }
136 
137     return 0;
138 }