AC自动机 学习笔记【AC自动机】【字符串】【字典树】

作者: wjyyy 分类: AC自动机,KMP,字典树,字符串,学习笔记 发布时间: 2018-09-01 15:44

点击量:86

AC 自动机是一种方便的多模式串匹配算法。基于字典树,用到了类似KMP的思维。

AC 自动机与 KMP 不同的是,AC 自动机可以同时匹配多个模式串,而复杂度不会达到太高。如果用 KMP 多次匹配字符串,复杂度就是 $O(k(n+m))$。

我们知道,如果让一个字符串头对头或者完全匹配其他字符串,用字典树来匹配是最为方便的。但是如果匹配过程中发现当前节点没有目标儿子,就发生了失配。在 KMP 字符串匹配中,失配可以跳到给当前位置预处理出的 nxt,继续匹配。

而 AC 自动机在字典树上,我们如何找出每个节点失配位置呢?我们知道,像 KMP 一样,失配位置是唯一确定的。而在字典树上,一条路径唯一对应了一个子串,因此也是唯一确定的。

KMP 中的 nxt 数组是由变量 j 承接了前一个位置的 nxt,我们考虑在 AC 自动机中也让失配指针从父节点转移过来。那么如此一来,当前节点(设为’c’)的失配指针就会从当前父节点的失配指针一直沿失配指针递归,找到第一个有以’c’字符为儿子的节点,把当前节点的失配指针连接到这个节点的’c’儿子上。如此做下去,会发现有了失配指针的树变成了一个图。但是如果上面的回溯过程找到根了还没有找到怎么办?

正常情况下,字典树的根是不带任何字符的,也就是说它是一个空节点,也是重新匹配的开始。如果我们一开始匹配就出现了失误,也就是根节点都没有这个儿子,我们当然要留在自己位置上继续做,因此根节点的失配指针指向自己(同时防止越界)。同理,根节点的儿子们失配指针指向根节点,因为在这里失配了,接下来只有两种情况:一是根节点也没有这个儿子,于是回归到根节点的一般情况;二是根节点有这个儿子,根节点有这个儿子我们就通过当前节点的失配指针先走到根节点,再走到这个儿子去。

于是,我们的 Trie 树变成了 Trie 图。

可以根据上面的前两幅图更清楚的了解 AC 自动机,其中红色边是 fail 边。我们可以发现一个有趣的事情,fail 指针可以构成一棵有向树,注意到每条单独的链都没有分支,而且一条链上的字母总是一致的,因此可能在以后的题目或者优化中出现。(就像 KMP 的 nxt 一样)

实际上在构建 AC 自动机时,我们的失配指针并不这样建。为了减小常数(也许是这个原因),我们认为当前节点如果没有儿子’c’,就把当前节点代表’c’儿子的指针连向当前节点失配指针的’c’儿子。

因为一个点的失配指针指向的节点总是比这个点浅,所以我们用 BFS 来做,深度较浅的点总比深度深的点先被访问,也因此,当前节点的失配指针的’c’儿子一定有位置,即使不是它真正的儿子,也一定是它通过失配指针索引得到的。

在最坏的情况下,如果失配指针回溯的过程中怎么也找不到这样的儿子,自然而然当前节点的’c’儿子就连向根了。

与字典树类似,AC 自动机成功匹配就是找到了一个单词的结尾,我们在构建字典树时就应该把每个模式串的结尾做上标记。但是如果两个模式串有包含关系怎么办?

有两种方法可以完成,一是访问到每个节点时暴力跳 fail 指针,直到递归到根,对答案的贡献就是这条路径的标记数;二是构建 fail 树,跳就是沿着 fail 树在跳,只需要预处理出 fail 树上每个节点到根路径上标记的数目(前缀和),就可以在当前节点记录答案。看上去第二种方法复杂度更优,但是它有局限性。也就是当确切地统计每个模式串出现的次数时,这种直接用 fail 树统计出现次数和的方法不能适用。

UPD:如果每个模式串答案只统计一次,那么可以在访问到一个已经被访问的节点后直接返回,因为后面连接的fail指针的答案已经被统计过了,也就没有必要统计。用到了记忆化搜索的思想。

UPD on 2019.5.6

上面斜体部分说起来并不确切,当时我对离线思想并不是很理解,因此没有提出更优的做法。事实上我们在访问过的位置做标记,然后在 fail 树上统计子树的标记次数就可以了。

原来的代码片段of AC自动机简单版:

void match()
{
    int ans=0;
    scanf("%s",s);
    node *now=root;
    for(int i=0;s[i]!='\0';++i)
    {
        now=now->ch[s[i]-'a'];
        ans+=now->End;
        now->End=0;//End置为0表示以后不再做出贡献
        node *p=now;
        while(p!=root)
        {
            p=p->fail;
            ans+=p->End;//同理
        }
    }
    printf("%d\n",ans);
}

我们与其置为 0,不如置为 -1 表示是后面的 fail 全部做过,也就是后面的fail指针指向的地方,无论原来的数字是多少,在访问过后都变成了 0,因此置为 -1 表示访问过的标记。

改动后的代码:

void match()
{
    int ans=0;
    scanf("%s",s);
    node *now=root;
    for(int i=0;s[i]!='\0';++i)
    {
        now=now->ch[s[i]-'a'];
        if(~now->End)//如果是-1就不统计答案
            ans+=now->End;
        now->End=-1;
        node *p=now;
        while(p!=root&&~p->End)
        {
            p=p->fail;
            ans+=p->End;
            p->End=-1;//置为-1
        }
    }
    printf("%d\n",ans);
}

Code of luoguP3796:AC自动机加强版

这个题要注意重复的模式串统计问题

#include<cstdio>
#include<cstring>
#include<vector>
using std::vector;
vector<int> same[155];//与某一个模式串相同的模式串编号
struct node
{
    int End,num;//num表示相同模式串个数,End表示是否为结束位置
    node *ch[26];
    node *fail;
    node()
    {
        memset(ch,0,sizeof(ch));
        fail=NULL;
        End=0;
        num=0;
    }
    void build(char *c,int i)//构建字典树
    {
        if(*c=='\0')
        {
            End=1;
            if(!num)
                num=i;
            same[num].push_back(i);//如果发现这里已经有单词结束了,那么一定是重复的,直接向原来的后面加编号就好了
            return;
        }
        if(!ch[*c-'a'])
            ch[*c-'a']=new node();
        ch[*c-'a']->build(c+1,i);
    }
}*root=new node();
char t[200][200];
node *q[1000011];//用队列完成BFS
int l=0,r=0;
void Fail()//构建fail指针
{
    root->fail=root;//没有这句话貌似也可以,为了保险起见,防止越界
    for(int i=0;i<26;++i)//根节点的儿子失配指针都指向自己
        if(!root->ch[i])//没有这个儿子就指向失配指针的这个儿子,而失配指针是自己,为了不紊乱和方便,这个儿子就指向自己
            root->ch[i]=root;
        else
        {
            root->ch[i]->fail=root;//设置失配指针
            q[++r]=root->ch[i];
        }
    while(l<r)
    {
        node *p=q[++l];
        for(int i=0;i<26;++i)
            if(p->ch[i])
            {
                p->ch[i]->fail=p->fail->ch[i];//有这个儿子就设置失配指针到自己的失配指针,自己的失配指针指向的地方一定已经完成工作了
                q[++r]=p->ch[i];
            }
            else
                p->ch[i]=p->fail->ch[i];
    }
    return;
}
char s[1000010];
int cnt[155];
void match()
{
    int ans=0;
    scanf("%s",s);
    node *now=root;
    for(int i=0;s[i]!='\0';++i)//开始匹配
    {
        now=now->ch[s[i]-'a'];
        cnt[now->num]+=now->End;
        node *p=now;
        while(p!=root)//暴力跳fail
        {
            p=p->fail;
            cnt[p->num]+=p->End;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n)
    {
        root=new node();
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
        {
            scanf("%s",t[i]);
            root->build(t[i],i);
        }
        Fail();
        match();
        int mx=0;
        for(int i=1;i<=n;++i)
        {
            for(vector<int>::iterator it=same[i].begin();it!=same[i].end();++it)//处理相同模式串
                cnt[*it]=cnt[i];
            if(mx<cnt[i])
            {
                cnt[0]=1;
                mx=cnt[i];
            }
            else if(mx==cnt[i])
                ++cnt[0];
        }
        printf("%d\n",mx);
        for(int i=1;i<=n;++i)
            if(cnt[i]==mx)
                printf("%s\n",t[i]);
        scanf("%d",&n);
    }
    return 0;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【AC自动机学习笔记】_基本不记得了……at 2019/1/10 19:26_ […]

/* */