{AC自动机}

开始搞ac自动机啦

之前看着费劲的现在轻易就理解了，剩下的就是多做题了

加油！！！

先来个模板题

  1 #include <cstdio>
  2 #include <cstring>
  3 const int maxn=1000010;
  4 
  5 int n;
  6 char s[maxn],p[maxn];
  7 struct Trie
  8 {
  9     int ct;
 10     Trie *fail;
 11     Trie *nex[26];
 12     Trie()
 13     {
 14         ct=0;
 15         fail=NULL;
 16         for(int i=0;i<26;i++)
 17             nex[i]=NULL;
 18     }
 19 };
 20 
 21 Trie *rt;
 22 Trie *q[maxn];
 23 int head,tail;
 24 void inser(char *p)
 25 {
 26     Trie *tp=rt;
 27     int pl=strlen(p);
 28     for(int i=0;i<pl;i++)
 29     {
 30         int k=p[i]-'a';
 31         if(tp->nex[k]==NULL)
 32         {
 33             Trie *node=new Trie();
 34             tp->nex[k]=node;
 35         }
 36         tp=tp->nex[k];
 37     }
 38     tp->ct++;
 39 }
 40 void getfail()
 41 {
 42     q[tail++]=rt;
 43     while(head!=tail)
 44     {
 45         Trie *now=q[head++];
 46         Trie *temp=NULL;
 47         for(int i=0;i<26;i++)
 48         {
 49             if(now->nex[i]!=NULL)
 50             {
 51                 if(now==rt) now->nex[i]->fail=rt;  //
 52                 else
 53                 {
 54                     temp=now->fail;
 55                     while(temp!=NULL)
 56                     {
 57                         if(temp->nex[i]!=NULL)
 58                         {
 59                             now->nex[i]->fail=temp->nex[i];
 60                             break;
 61                         }
 62                         temp=temp->fail;
 63                     }
 64                     if(temp==NULL) now->nex[i]->fail=rt; //
 65                 }
 66                 q[tail++]=now->nex[i];
 67             }
 68         }
 69     }
 70 }
 71 int query(char *s)
 72 {
 73     int len=strlen(s);
 74     int ans=0;
 75     Trie *now=rt;
 76     for(int i=0;i<len;i++)
 77     {
 78         int k=s[i]-'a';
 79         while(now->nex[k]==NULL&&now!=rt)
 80             now=now->fail;
 81         now=now->nex[k];
 82         if(now==NULL) now=rt;
 83         Trie *temp=now;
 84         while(temp!=rt&&temp->ct!=-1)
 85         {
 86             ans+=temp->ct;
 87             temp->ct=-1;
 88             temp=temp->fail;
 89         }
 90     }
 91     return ans;
 92 }
 93 int main()
 94 {
 95     while(scanf("%d",&n)!=EOF)
 96     {
 97         head=tail=0;
 98         rt=new Trie();
 99         for(int i=0;i<n;i++)
100         {
101             scanf("%s",p);
102             inser(p);
103         }
104         getfail();
105         scanf("%s",s);
106         if(query(s)) puts("YES");
107         else puts("NO");
108     }
109 }

View Code

题目链接：HDU 2222

第一次自己不看模板写好。。

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int maxn=1000010;
  5 char s[maxn],p[55];
  6 int n;
  7 struct Trie
  8 {
  9     int ct;
 10     Trie *fail;
 11     Trie *nex[26];
 12     Trie()
 13     {
 14         ct=0;
 15         fail=NULL;
 16         for(int i=0;i<26;i++) nex[i]=NULL;
 17     }
 18 };
 19 
 20 Trie *rt;
 21 Trie *q[maxn];
 22 int head,tail;
 23 void inser(char *s)
 24 {
 25     int len=strlen(s);
 26     Trie *now=rt;
 27     for(int i=0;i<len;i++)
 28     {
 29         int k=s[i]-'a';
 30         if(now->nex[k]==NULL) now->nex[k]=new Trie();
 31         now=now->nex[k];
 32     }
 33     now->ct++;
 34 }
 35 void getfail()
 36 {
 37     q[tail++]=rt;
 38     while(head!=tail)
 39     {
 40         Trie *now=q[head++];
 41         Trie *temp=NULL;
 42         for(int i=0;i<26;i++)
 43         {
 44             if(now->nex[i]!=NULL)
 45             {
 46                 if(now==rt) now->nex[i]->fail=rt;
 47                 else
 48                 {
 49                     temp=now->fail;
 50                     while(temp!=NULL)
 51                     {
 52                         if(temp->nex[i]!=NULL)
 53                         {
 54                             now->nex[i]->fail=temp->nex[i];
 55                             break;
 56                         }
 57                         temp=temp->fail;
 58                     }
 59                     if(temp==NULL) now->nex[i]->fail=rt;
 60                 }
 61                 q[tail++]=now->nex[i];
 62             }
 63 
 64         }
 65     }
 66 }
 67 
 68 int query(char *s)
 69 {
 70     int len=strlen(s);
 71     Trie *now=rt;
 72     int ans=0;
 73     for(int i=0;i<len;i++)
 74     {
 75         int k=s[i]-'a';
 76         while(now->nex[k]==NULL&&now!=rt) now=now->fail;
 77         now=now->nex[k];
 78         if(now==NULL) now=rt;
 79         Trie *temp=now;
 80         while(temp!=rt&&temp->ct!=-1)
 81         {
 82             ans+=temp->ct;
 83             temp->ct=-1;
 84             temp=temp->fail;
 85         }
 86     }
 87     return ans;
 88 }
 89 int main()
 90 {
 91     int t;
 92     scanf("%d",&t);
 93     while(t--)
 94     {
 95         rt=new Trie();
 96         scanf("%d",&n);
 97         while(n--)
 98         {
 99             scanf("%s",p);
100             inser(p);
101         }
102         getfail();
103         scanf("%s",s);
104         printf("%d
",query(s));
105     }
106 }

View Code