AC自动机

http://baike.baidu.com/view/8150013.htm

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

今天看到这道题以为是KMP 刚学完想拿来练手谁知写完超时。去discuss看了看说是用AC自动机过的今天也没什么安排就去了解了下它是建立在KMP和trie树基础上的一种高效串匹配的算法

先将字符串建成一个字典树标记每个字符串的尾部建完之后输入待匹配的字符串这是只对这个字符串进行循环查找即可判断每个字符是否是在字典树里出现当循环到一个字符串的尾部时 num就会加上这个字符串的数量。

看着别人的模板打了一晚上有些地方还是模模糊糊的不过还是学了点东西

View Code

  1 #include<stdio.h>
  2 #include <iostream>
  3 #include<string.h>
  4 using namespace std;
  5 struct node
  6 {
  7     int count;//标记字符串的结束 和数量
  8     struct node *next[28];//指向 26个字母的子节点 最多只有26个 一个节点有26个字母域
  9     struct node *fail;//失败指针 与KMP的next函数类似
 10     node()//初始化函数 将节点的26个指针域都清空
 11     {
 12         fail = NULL;
 13         count = 0;
 14         memset(next,NULL,sizeof(next));
 15     }
 16 }*q[1000001];
 17 int tail,head;//队列的头尾
 18 char str[1000001];    
 19 void creat(char *c,struct node *root)//建立字典树
 20 {
 21     int i = 0,num;
 22     struct node *p = root;
 23     while(c[i])
 24     {
 25         num = c[i]-97;
 26         if(p->next[num]==NULL)
 27         {
 28             p->next[num] = new node;//若为空 为其创立新节点
 29         }
 30         i++;
 31         p=p->next[num];
 32     }
 33     p->count++;//到了字符串尾部 就加一
 34     
 35 }
 36 /*
 37 在字典树上构造fail指针。构造失败指针的过程概括起来就一句话：
 38 设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，
 39 他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。
 40 如果一直走到了根节点都没找到，那就把失败指针指向根节点。
 41 所以构造fail指针 需要用到BFS。 保证是按层遍历字典树。
 42 */
 43 void bfail(struct node *root)//利用队列BFS实现层遍历 来找fail指针
 44 {
 45     int i;
 46     head = 0;
 47     tail = 0;
 48     root->fail = NULL;
 49     q[tail++] = root;
 50     while(head!=tail)
 51     {
 52         struct node *temp=q[head++];
 53         struct node *p = NULL;
 54         for(i = 0; i < 26 ; i++)
 55         {
 56             if(temp->next[i]!=NULL)
 57             {
 58                 if(temp==root)
 59                     temp->next[i]->fail = root;//所有根节点的子节点都指向根节点
 60                 else
 61                 {
 62                     p = temp->fail;
 63                     while(p!=NULL)
 64                     {
 65                         if(p->next[i]!=NULL)//找到一个节点的子节点有i字母 
 66                         {
 67                             temp->next[i]->fail=p->next[i];//设为fail指针
 68                             break;
 69                         }
 70                         p=p->fail;//循环找 与kmp类似
 71                     }
 72                     if(p==NULL)
 73                         temp->next[i]->fail = root;//若为空 指向根节点
 74                 }
 75                 q[tail++] = temp->next[i];
 76             }
 77         }
 78     }
 79 }
 80 /*
 81 匹配过程分两种情况：
 82 (1)当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，
 83 此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；
 84 (2)当前字符不匹配，则去当前节点失败指针所指向的字符继续匹配，
 85 匹配过程随着指针指向root结束。重复这2个过程中的任意一个，直到模式串走到结尾为止。
 86 */
 87 int ac(struct node *root)
 88 {
 89     int i=0,k=strlen(str),d,num = 0;
 90     struct node *p = root;
 91     for(i = 0 ;i < k ; i++)
 92     {
 93         d = str[i]-97;
 94         while(p->next[d]==NULL&&p!=root)//字典树里找不到i字符 退回根节点
 95             p=p->fail;
 96         p=p->next[d];
 97         if(p==NULL)
 98             p = root;
 99         struct node *temp = p;
100         while(temp!=root&&temp->count!=-1)
101         {
102             num+=temp->count;
103             temp->count = -1;//避免重复记录
104             temp = temp->fail;
105         }
106     }
107     return num;
108 }
109 int main()
110 {
111     int i,j,n,t;
112     char c[52];
113     scanf("%d",&t);
114     while(t--)
115     {
116         scanf("%d%*c",&n);
117         struct node *root = new node;
118         for(i = 1; i <= n ; i++)
119         {
120             gets(c);
121             creat(c,root);
122         }
123         gets(str);
124         bfail(root);
125         printf("%d\n",ac(root));
126     }
127     return 0;
128     
129 }