Match:Keywords Search(AC自动机模板)(HDU 2222)

　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　多模匹配

　　题目大意：给定很多个字串A，B，C，D，E....，然后再给你目标串str字串，看目标串中出现多少个给定的字串。

　　经典AC自动机模板题，不多说。

　　

 #include <iostream>

 #include <algorithm>

 #include <functional>

 #include <string.h>

 #define MAX 26

 using namespace std;

 struct node

 {

     node *fail, *next[MAX];

     int count;

 }Mem_Pool[], *Trie_Queue[];

 static int Used_Node;

 static char pattern[], target[];

 struct node *Get_New_Node(void);

 void Insert(struct node*);

 void Build_AC_Automation(struct node* const);

 static int Query(struct node* const);

 int main(void)

 {

     int case_sum, pattern_sum;

     scanf("%d", &case_sum);

     while (case_sum--)

     {

         Used_Node = ;

         node *root = Get_New_Node();//每一次都拿一个新的根

         scanf("%d", &pattern_sum);

         getchar();

         while (pattern_sum--)

             Insert(root);

         Build_AC_Automation(root);

         gets(target);

         printf("%d\n", Query(root));

     }

 }

 struct node *Get_New_Node(void)

 {

     Mem_Pool[Used_Node].count = ;

     Mem_Pool[Used_Node].fail = NULL;

     memset(Mem_Pool[Used_Node].next, , sizeof(struct node *)*MAX);

     return &Mem_Pool[Used_Node++];

 }

 void Insert(struct node *root)

 {

     gets(pattern);

     node *p = root;

     int index;

     for (int i = ; pattern[i] != '\0'; i++)

     {

         index = pattern[i] - 'a';

         if (p->next[index] == NULL)

             p->next[index] = Get_New_Node();

         p = p->next[index];

     }

     p->count++;//表示这个位置包含着一个字符，如果有多个则叠加就可以了。

 }

 void Build_AC_Automation(struct node *const root)//自动机的构造例程，其实就是个BFS

 {

     root->fail = NULL;

     int head = , back = ;

     node *out = NULL, *tmp = NULL;

     Trie_Queue[back++] = root;

     while (head != back)

     {

         out = Trie_Queue[head++];

         for (int i = ; i < MAX; i++)//枚举所有情况

             if (out->next[i] != NULL)

             {

                 if (out == root)

                     out->next[i]->fail = root;//如果out自己就是根，那么直接将其子节点的失败指针指向自己就好了

                 else

                 {

                     for (tmp = out->fail; tmp != NULL; tmp = tmp->fail)

                         if (tmp->next[i] != NULL)

                         {

                             out->next[i]->fail = tmp->next[i];

                             //如果还找到在其他地方找到和他一样的元素，那么我们就把失败指针指向这个元素

                             break;

                         }

                     if (tmp == NULL)

                         out->next[i]->fail = root;

                 }

                 Trie_Queue[back++] = out->next[i];

             }

     }

 }

 static int Query(struct node *const root)

 {

     int ans = ;

     node *tmp = root, *other = NULL;

     //tmp是跟着目标串的移动而移动的，other指针则表示在tire树的其他位置看还能不能匹配到其他字串

     for (int i = ; target[i] != '\0'; i++)

     {

         int index = target[i] - 'a';

         while (tmp->next[index] == NULL && tmp != root)

             tmp = tmp->fail;//沿着失败指针一直走

         tmp = tmp->next[index];

         tmp = (tmp == NULL) ? root : tmp;//检查如果是已经是root了，直接跳出来就好了

         for (other = tmp; other != root && other->count != -; other = other->fail)

         {

             ans += other->count;

             other->count = -;//标记一下，不要重复扫描

         }

     }

     return ans;

 }