指针版-AC自动机-Keyword Search|玄武密码

大家都不喜欢指针，但是这个AC自动机仿佛不用不行……

先引用我最喜欢的话：“AC自动机，不是自动AC的机器。” 如果写不好还可能一直WA

AC自动机是KMP与Trie树的完美结合，适用于多字符串匹配，这与KMP的单串不同

首先是一棵Trie树

Trie树

记得建空节点做根，有大神忘记了建，直想砸键盘。

然后标准建树

如果用指针的话申请空间冷静一点

下一步就是构建fail指针，虽然我喜欢把它叫next，与KMP一致

幸好找到了好的版子，不然就很难搞

因为fail指针的构建顺序必须由上到下

即：fail是从下面的节点指向上面的节点的，这样不会漏配

So用BFS会很棒。

左面就是一个手画的树

void build(){
    root->next=NULL;//根节点无fail
    push(root);//根节点入队
    while(!empty()){//BFS开始
        TREE *i=front();//提取队首元素
        for(int j=0;j<26;j++){//对每一个字母进行处理，尝试搜索
            if(i->s[j]!=NULL){//搜到
                if(i==root)i->s[j]->next=root;//是和根节点直接连的回根
                else
                {
                    TREE* p=i->next;//和搜索的点的fail指针的下节点找
                    while(p!=NULL)//继续找，所有fail都符合要求 
                    {
                        if(p->s[j]!=NULL)//fail指针处有和j字母一样的点 
                        {
                            i->s[j]->next=p->s[j];//更新结束 
                            break;
                        }
                        p=p->next;//fail的fail也符合要求 
                    }
                    if(p==NULL) i->s[j]->next=root;//无匹配，回根 
                }
                q[++e]=i->s[j];//结果入队 
            }
        }
    }
}

经过一番建立，我们将所有的fail构建完成~~

长这样:

ACauto最好自己再画一个图，这样会更好的理解

然后就要搜索了，搜索和建立很像

补下：搜索的解释，上次忘写了，自己很吃亏，尴尬

void ffind(){//搜索函数 
    int j=0;//从0号位开始搜 
    TREE *p=root;//另一方面树上从根节点走起 
    while(st[j])
    {
        int i=st[j]-'a';//不解释 
        while(p->s[i]==NULL && p!=root) p=p->next;//没找着，就顺着fail往下走 
        p=p->s[i];//这时只可能有两种可能，一是真没有，二是找着一个 
        if(p==NULL)p=root;//没有我们直接回根，相当于重置树上指针 
        TREE *k=p;//这个是找着后用的 
        while(k!=root && k->endt!=-1)//去找 
        {
            ans+=k->endt;//有结尾标记，这个是根据KeywordSearch的题意 
            k->endt=-1;//为了防止重复计算 ，这个也是题意 
            k=k->next;//到所有的fail指针处找 
        }
        j++;
    }
}

如果是搜是否匹配或出现次数，在结尾写cnt计数即可

但如果要算匹配长度，我们就要打标记，再dfs一遍，像玄武密码一样

下面补上题和码

[模板]Keyword Search

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #define  L 1010101 
  6 using namespace std;
  7 struct TREE{
  8     TREE *next,*s[26];
  9     char dat;
 10     int endt;
 11     TREE(){
 12         next=NULL;
 13         memset(s,0,sizeof s);
 14         dat=endt=0;
 15     }
 16 };
 17 TREE *q[9999999];
 18 int f=0,e=0;
 19 TREE *root;
 20 int n,ans=0;
 21 char ch[L],st[L];
 22 void add(char *now){
 23     TREE *i=root;
 24     int j=0;
 25     while(now[j]){
 26         int k=now[j]-'a';
 27         if(i->s[k]==NULL)
 28             i->s[k]=new TREE();
 29         i=i->s[k];
 30         j++;//cout<<j<<endl;getchar();puts("P");
 31     }
 32     i->endt++;
 33 }
 34 bool empty(){
 35     if(e==f){
 36         return true;
 37     }
 38     return false;
 39 }
 40 void push(TREE *i){
 41     e++;
 42     q[e]=i;
 43 }
 44 TREE* front(){
 45     if(empty())return NULL;
 46     f++;
 47     return q[f];
 48 }
 49 void build(){
 50     root->next=NULL;
 51     push(root);
 52     while(!empty()){
 53         TREE *i=front();
 54         for(int j=0;j<26;j++){
 55             if(i->s[j]!=NULL){
 56                 if(i==root) i->s[j]->next=root;
 57                 else
 58                 {
 59                     TREE* p=i->next;
 60                     while(p!=NULL)
 61                     {
 62                         if(p->s[j]!=NULL)
 63                         {
 64                             i->s[j]->next=p->s[j];
 65                             break;
 66                         }
 67                         p=p->next;
 68                     }
 69                     if(p==NULL) i->s[j]->next=root;
 70                 }
 71                 q[++e]=i->s[j];
 72             }
 73         }
 74     }
 75 }
 76 void ffind(){
 77     int j=0;
 78     TREE *p=root;
 79     while(st[j])
 80     {
 81         int i=st[j]-'a';
 82         while(p->s[i]==NULL && p!=root) p=p->next;
 83         p=p->s[i];
 84         if(p==NULL)p=root;
 85         TREE *k=p;
 86         while(k!=root && k->endt!=-1)
 87         {
 88             ans+=k->endt;
 89             k->endt=-1;
 90             k=k->next;
 91         }
 92         j++;
 93     }
 94 }
 95 int main(){
 96     int T;
 97     scanf("%d",&T);
 98     while(T--){
 99         root=new TREE();
100         ans=0;        
101         scanf("%d",&n);
102         for(int i=1;i<=n;i++){
103             scanf("%s",ch);
104             add(ch);
105         }
106         scanf("%s",st);
107         build();
108         ffind();
109         printf("%d
",ans);        
110     } 
111     return 0;
112 }
View Code

[稍有思考][还是模板]玄武密码

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #define L 111111111
  5 #define N 111111
  6 using namespace std;
  7 struct ACauto{
  8     ACauto *next,*s[4];
  9     int endp,DeepinC;
 10     bool mark;
 11     ACauto(){
 12         next=NULL;
 13         memset(s,0,sizeof s);
 14         mark=DeepinC=endp=0;
 15     }
 16 }*root;
 17 struct Myqueue{
 18     ACauto *Q[9999999];int f,e;
 19     bool empty(){
 20         if(e==f)return true;
 21         return false;
 22     }
 23     void push(ACauto *k){
 24         e++;
 25         Q[e]=k;
 26     }
 27     ACauto* front(){
 28         if(empty())return NULL;
 29         f++;
 30         return Q[f];
 31     }
 32 }q;
 33 int n,ans=0,cnt=0;
 34 char st[L],ch[N][111];
 35 inline int turn(char ch){
 36     switch(ch){
 37         case 'E':return 0;
 38         case 'W':return 1;
 39         case 'S':return 2;
 40         default :return 3;
 41     }
 42 }
 43 void add(char *c){
 44     ACauto *i=root;
 45     int j=0;
 46     while(c[j]){
 47         int k=turn(c[j]);
 48         if(i->s[k]==NULL)
 49             i->s[k]=new ACauto();
 50         i=i->s[k];
 51         i->DeepinC=j+1;
 52 //        cout<<c[j]<<" "<<i->DeepinC<<endl;
 53         j++;
 54     }
 55     i->endp++;
 56 }
 57 void build(){
 58     root->next=NULL;
 59     q.push(root);
 60     while(!q.empty()){
 61         ACauto *i=q.front();
 62         for(int j=0;j<4;j++){
 63             if(i->s[j]!=NULL){
 64                 if(i==root) i->s[j]->next=root;
 65                 else{
 66                     ACauto *p=i->next;
 67                     while(p!=NULL){
 68                         if(p->s[j]!=NULL){
 69                             i->s[j]->next=p->s[j];
 70                             break;
 71                         }
 72                         p=p->next;
 73                     }
 74                     if(p==NULL) i->s[j]->next=root;
 75                 }
 76                 q.push(i->s[j]);
 77             }
 78         }
 79     }
 80 }
 81 void ffind(char *ser){
 82     int j=0;
 83     ACauto *p=root;
 84     while(ser[j]){
 85         int i=turn(ser[j]);
 86         while(p->s[i]==NULL&&p!=root){
 87             p=p->next;
 88             p->mark=1;//cout<<p<<" INP  "<<j<<" "<<ser[j]<<" Depth: "<<p->mark<<" "<<p->DeepinC<<endl;
 89         }
 90         p=p->s[i];
 91         if(p==NULL)p=root;
 92         ACauto *k=p;
 93         while(k!=root && k->endp!=-1){
 94             k->mark=1;
 95             k->endp=-1;
 96             k=k->next;//cout<<k<<" INK  "<<j<<" "<<ser[j]<<" Depth: "<<k->mark<<" "<<k->DeepinC<<endl;
 97         }
 98 //        cout<<k<<" OUTK "<<j<<" "<<ser[j]<<" Depth: "<<k->mark<<" "<<k->DeepinC<<endl;
 99         j++;
100     }
101 }
102 void ser(char *c){
103     ACauto *i=root;
104     int j=0;
105     int lsans=0;
106     bool la=1;
107     while(c[j]){
108         int k=turn(c[j]);
109         i=i->s[k];
110         if(i->mark)ans=max(i->DeepinC,ans);
111         j++;
112     }
113 }
114 int main(){
115     int len;
116     root=new ACauto();
117     scanf("%d%d",&len,&n);
118     scanf("%s",st);
119     for(int i=1;i<=n;i++) {
120         scanf("%s",ch[i]);
121         add(ch[i]);
122     }
123     build();
124     ffind(st);
125     for(int i=1;i<=n;i++){
126         ans=0;
127         ser(ch[i]);
128         printf("%d
",ans);
129     }
130     return 0;
131 }
View Code
Miemeng真的蒻
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/kalginamiemeng/p/11021748.html