字符串模板--AC自动机

前言:学习AC自动机

1.AC自动机?

AC自动机简称为树上KMP,这里的树是指trie树,KMP是字符串单一匹配的一种方法.学习AC自动机的前提是这两个算法都要掌握.AC自动机作为两者有机的结合,一定程度上弥补了KMP算法对单一匹配的不足(nxt数组只能对应一个匹配串),在trie树上能实现多对一的匹配.想想利用KMP算法我们要对每一个匹配串建立nxt数组,在trie树上利用fail指针即可.算法效率可提高.

2.AC自动机的构建.

I.构建trie树.

没错先构建trie树,但注意是对匹配串构建(肯定啊,主串只有一条)

II.构建fail指针.

跟KMP中nxt数组类似,fail数组也指字符最长前缀等于后缀的长度.那么在trie树上的''nxt''数组怎么求解呢?这里我们用BFS实现.首先将root定义为0,我们将与root直接相连的child的fail指向root,并加入队列,由第一层的child就此扩展.以后每扩展节点,它拥有26child的实点或者虚点.对于实点求fail,我们看它的father指向的fail节点的直接child看是否相同,有就直接指向它,没有则跳向fail的fail,看它的直接child找不找的相同的...在这个过程中最坏情况最终指向根结点.对于虚点的话,我们直接将它指向father的fail对应child.为什么这做在匹配时解释.code:

void getfail()
{
    queue<int> q;
    for(R int i=0;i<26;++i){
        if(tire[0][i]){
            fail[tire[0][i]]=0;
            q.push(tire[0][i]);
        }
    }
    while(q.size()){
        int now=q.front();
        q.pop();
        for(R int i=0;i<26;++i){
            if(tire[now][i]){
                fail[tire[now][i]]=tire[fail[now]][i];
                q.push(tire[now][i]);    
            }
            else tire[now][i]=tire[fail[now]][i];
        }
    }
}

III.字符串匹配.

这次我们是将主串的每一字符放在trie树上跑,每次对现在的id跳fail,这样我们跑着在匹配串中的相同字符串都可跑到,在这里我们对虚点就可直接跳fail(当主串失配时),这样我们就不用对失配的地方从头开始匹配.此时其实不是trie树是trie图了.以LG板子为例,code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define e exit(0)
#define R register
const int maxn=2*1e6+10;
char t[maxn],s[maxn];
int n,lent,lens,cnt,tire[10000007][27],fail[maxn],cntword[maxn<<1],ans;
void insert(string t)
{
    int root=0;
    for(R int i=0;i<lent;++i){
        int word=t[i]-'a';
        if(!tire[root][word])
            tire[root][word]=++cnt;
        root=tire[root][word];
    }
    ++cntword[root];
}
void getfail()
{
    queue<int> q;
    for(R int i=0;i<26;++i){
        if(tire[0][i]){
            fail[tire[0][i]]=0;
            q.push(tire[0][i]);
        }
    }
    while(q.size()){
        int now=q.front();
        q.pop();
        for(R int i=0;i<26;++i){
            if(tire[now][i]){
                fail[tire[now][i]]=tire[fail[now]][i];
                q.push(tire[now][i]);    
            }
            else tire[now][i]=tire[fail[now]][i];
        }
    }
}
int ask(string s)
{
    ans=0;
    int now=0;
    for(R int i=0;i<lens;++i){
        int word=s[i]-'a';
        now=tire[now][word];
        for(R int j=now;j&&cntword[j]!=-1;j=fail[j]){
            ans+=cntword[j];
            cntword[j]=-1;
        }
    }
    return ans;
}
int main()
{
//    freopen("s.in","r",stdin);
//    freopen("s.out","w",stdout);
    scanf("%d",&n);
    while(n--){
        scanf("%s",t);
        lent=strlen(t);
        insert(t);
    }
    fail[0]=0;
    getfail();
    scanf("%s",s);
    lens=strlen(s);
    printf("%d",ask(s));
    return 0;
}