AC自动机……………更新中

时间：2010-11-29 来源：头发凌乱着
题意：给出n个字符串keyword，最后给出一个模式串string，问有多少个keyword是string的子串；输出个数；
                   1: /* 
                   2:  * File:   main.cpp
                   3:  * Author: 小陈
                   4:  * Created on 2010年11月29日, 下午3:55
                   5:  */
                   6: #include <cstdlib>
                   7: #include<iostream>
                   8: using namespace std;
                   9: struct node {
                  10:     int count;
                  11:     node *fail;
                  12:     node * next[26];
                  13:     node() {
                  14:         count = 0;
                  15:         fail = NULL;
                  16:         memset(next, NULL, sizeof (next));
                  17:     }
                  18: };
                  19: node *q[500001]; //模拟队列，方便用于bfs构造失败指针；
                  20: int head, tail; //队列的头尾指针
                  21: char keyword[60]; //子串
                  22: char str[1000001]; //模式串
                  23: void insert(char *str, node *root) {
                  24:     node *p = root;
                  25:     int i = 0, index;
                  26:     while (str[i]) {
                  27:         index = str[i] - 'a';
                  28:         if (p->next[index] == NULL)
                  29:             p->next[index] = new node();
                  30:         p = p->next[index];
                  31:         i++;
                  32:     }
                  33:     p->count++;
                  34: }
                  35: void build(node *root) {
                  36:     root->fail = NULL;
                  37:     q[head++] = root;
                  38:     while (head != tail) {
                  39:         node *temp = q[tail++];
                  40:         node *p = NULL;
                  41:         for (int i = 0; i < 26; i++) {
                  42:             if (temp->next[i] != NULL) {
                  43:                 if (temp == root)
                  44:                     temp->next[i]->fail = root;
                  45:                 else {
                  46:                     p = temp->fail;
                  47:                     while (p != NULL) {
                  48:                         if (p->next[i] != NULL) {
                  49:                             temp->next[i]->fail = p->next[i];
                  50:                             break;
                  51:                         }
                  52:                         p = p->fail;
                  53:                     }
                  54:                     if (p == NULL)
                  55:                         temp->next[i]->fail = root;
                  56:                 }
                  57:                 q[head++] = temp->next[i];
                  58:             }
                  59:         }
                  60:     }
                  61: }
                  62: int query(node *root) {
                  63:     int i = 0, cnt = 0, index, len = strlen(str);
                  64:     node *p = root;
                  65:     while (str[i]) {
                  66:         index = str[i] - 'a';
                  67:         while (p->next[index] == NULL && p != root)
                  68:             p = p->fail;
                  69:         p = p->next[index];
                  70:         p = (p == NULL) ? root : p;
                  71:         node *temp = p;
                  72:         while (temp != root && temp->count != -1) {
                  73:             cnt += temp->count;
                  74:             temp->count = -1;
                  75:             temp = temp->fail;
                  76:         }
                  77:         i++;
                  78:     }
                  79:     return cnt;
                  80: }
                  81: int main(int argc, char** argv) {
                  82:     int n, t;
                  83:     scanf("%d", &t);
                  84:     while (t--) {
                  85:         head = tail = 0;
                  86:         node *root = new node();
                  87:         scanf("%d", &n);
                  88:         getchar();
                  89:         while (n--) {
                  90:             gets(keyword);
                  91:             insert(keyword, root);
                  92:         }
                  93:         build(root);
                  94:         scanf("%s", str);
                  95:         printf("%d\n", query(root));
                  96:     }
                  97:     return 0;
                  98: }
                  99:  
              
            
          
        
      
    
  
  