Keywords Search

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 using namespace std;
  6 
  7 const int kind=26;
  8 
  9 struct node {
 10     node *fail;     //失败指针
 11     node *next[kind];//Tire树每个节点的子节点个数
 12     int cot;        //是否为该单词的最后一个节点
 13     node()          //构造函数初始化
 14     {
 15         fail=NULL;
 16         cot=0;
 17         memset(next,0,sizeof(next));
 18     }
 19 }*q[500002];        //队列，方便用于bfs构造失败指针
 20 char str[1000001];  //模式串
 21 int head,tail;      //队列的头尾指针
 22 
 23 
 24 void inser(char *str,node *root)        //构造tire数；
 25 {
 26     node *p=root;
 27     int i=0,index;
 28     while(str[i])
 29     {
 30         index=str[i]-'a';
 31         if(p->next[index]==NULL)
 32             p->next[index]=new node();
 33         p=p->next[index];       //p指向i字符相等的节点
 34         i++;
 35     }
 36     p->cot++;       //在单词的最后一个节点是的cot加1，代表单词数加1；
 37 }
 38 
 39 void build_ac_automatio(node *root)         //写出fail的指向
 40 {
 41     int i;
 42     root->fail=NULL;
 43     q[head++]=root;             //bfs
 44     while(head!=tail)
 45     {
 46         node *temp=q[tail++];
 47         node *p=NULL;
 48         for(i=0;i<26;i++)
 49         {
 50             if(temp->next[i]!=NULL)         //当前的子节点i不为空
 51             {
 52                 if(temp==root)
 53                     temp->next[i]->fail=root;
 54                 else
 55                 {
 56                     p=temp->fail;               //记录一下当前节点失败节点指向那个节点
 57                     while(p!=NULL)              //直到找到
 58                     {
 59                         if(p->next[i]!=NULL)        //失败节点指向的节点的i子节点不为空的话，就和当前节点的i相等，即当前i的失败节点即为父节点失败节点指向的i子节点、
 60                         {
 61                             temp->next[i]->fail=p->next[i]; break;
 62                         }
 63                         p=p->fail;
 64                     }
 65                     if(p==NULL)
 66                         temp->next[i]->fail=root;
 67                 }
 68                q[head++]=temp->next[i];         //先把失败节点指向，再进入队列
 69             }
 70         }
 71     }
 72 }
 73 
 74 
 75 int query(node *root)           //查询
 76 {
 77     int i=0,cnt=0,index,len=strlen(str);
 78     node *p=root;
 79     
 80     while(str[i])
 81     {
 82         index =str[i]-'a';
 83         while(p->next[index]==NULL&&p!=root)        //当前节点失败，&& 第root节点
 84             p=p->fail;
 85         p=p->next[index];
 86         p=(p==NULL)?root:p;
 87         node *temp=p;
 88         while(temp!=root&&temp->cot!=-1)        //查询当前字符节点是否为结束字符， && 单词之前没有
 89         {
 90             cnt+=temp->cot;
 91             if(temp->cot>0)
 92                 temp->cot=-1;
 93             temp=temp->fail;
 94         }
 95         i++;
 96     }
 97     return cnt;
 98 }
 99 
100 int main()
101 {
102     int t,n,i;
103     char s[51];
104     scanf("%d",&t);
105     while(t--)
106     {
107         node root;
108         scanf("%d",&n);
109         for( i=0;i<n;i++)
110         {
111             //gets(s);
112             scanf("%s",s);
113             //getchar();
114             inser(s,&root);
115         }
116         build_ac_automatio(&root);
117         scanf("%s",str);
118         printf("%d
",query(&root));
119     }
120     return 0;
121 }
122
View Code
AC自动机
Sample Input
she
say
shr
her
yasherhs
Sample Output
有多个单词，在主串中出现过多少个单词、
构建字典树，建立fail指针直到求出结果