AC自动机模板题。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           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
         
           que; 45  46     for (i=0; i
          
           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
           
            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
            
             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 }