hdu 2222 AC自动机

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

hdu 2222 AC自动机的模板题，题意大楷是：给出一些单词，和一段文本，输出文本中出现的单词个数，重复的不计。

AC自动的原理和KMP的原理差不多，AC自动机的Fail指针和KMP的next数组的原理是一样的。

具体的AC自动机的阐述网上很多，在这里我就不画蛇添足了。

来看看我写的一个AC自动的代码吧，很丑陋不过可以过，嘿嘿！

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stdio.h>
using namespace std;
const int kind = 26; 

struct node{  
     node *fail;       //失败指针
     node *next[kind]; //Tire每个节点的26个子节点（最多26个字母）
     int count;        //是否为该单词的最后一个节点
     node(){           //构造函数初始化
        fail= NULL; 
        count=0; 
       for(int i = 0 ; i < kind ;++i)
          next[i] = NULL; 
     } 
};        
 void makeFailBFS(node* trie)
{
       node* root = trie;
       queue<node*> que;
       que.push(root);
       while(!que.empty())
       {
          node* front = que.front();
          que.pop();
          int i = 0;
          for( ; i < 26 ; ++i)
          {
            if(front->next[i] != NULL)
            {
                if(front == root)front->next[i]->fail = root;
                else
                {
                    node *tmp = front;
                    while(tmp->fail != NULL)
                    {
                      if(tmp->fail->next[i] != NULL)
                      {
                         front->next[i]->fail = tmp->fail->next[i];
                         break;
                      }
                      tmp = tmp->fail;
                    }
                    if(tmp->fail == NULL)
                       front->next[i]->fail = trie;
                }  
                que.push(front->next[i]);            
            }                    
          }
       }
}
 void buildTrie(node*trie , char*word)
{
  struct node*root=trie;
  for(int i = 0 ; word[i] ; ++i)
  {
    int x = word[i]-'a';
   // cout << x << endl;
    
    if(root->next[x]!= NULL)
    {
      root = root->next[x];
    }
    else
    {
        root->next[x] = new node;
        root = root->next[x];
    } 
    if(!word[i+1])
            root->count+=1;                                                                          
  }
}
inline void find(node *&trie , char*text)
{
       node *root = trie;
       int i = 0;
       int ans = 0;
       while(text[i])
       {
        int x = text[i]-'a';
        if(root->next[x] != NULL)
        {
          root = root->next[x];
          node * tmp = root;
          if(root != NULL && root->count > 0)
          {
            ans+=root->count;
            root->count =0;
          }
          while(tmp->fail != NULL && tmp->fail->count > 0)
          {
                  ans+=tmp->fail->count;
                  tmp->fail->count=0;
                  tmp = tmp->fail;
                  
          }               
          i++;
        }
        else
        {
            root = root->fail;

            if(root == NULL)
            {
               root = trie;
               i++;
             }
        
         } 
   
       }
       cout << ans << endl;
}
int main()
{
    int t , n , i=0;
    cin >> t;
  //  getchar();
    while(t--)
    { 
         struct node *trie = new node;
         cin >> n;
        
         char ch[20];
         gets(ch);//接收一个换行符 
         for(i = 0 ; i < n ; ++i)
         {
          char word[55];
          gets(word);
          buildTrie(trie,word); 
         }   
         char text[1000010];
         gets(text);
         makeFailBFS(trie);
         find(trie,text);   
    }
  

    return 0;
}