AC自动机学习笔记

AC自动机简介

自动机的一种，著名的多模匹配算法

可以理解为 Trie + KMP

结构

建立在字典树的基础上

先把所有要匹配的模式串全部塞到一个字典树上面

然后在上面添加一种指针

类似于 KMP 中的 nxt[] 数组，AC自动机中的每个节点有一个叫做 fail 的指针（失配指针）

与 KMP 类似，

fail 表示最长的相等前后缀，只不过不是一个字符串上面考虑，而是在整棵字典树上面考虑

fail就是从后缀的结尾指向前缀的结尾

举个例子

这张图是

she shr say her he

这五个字符串构建出来的AC自动机红色的是 fail

来看一眼左下角的那个点

他表示的字符串是 she

有一个后缀 he 正好是 her 的前缀，所以这个点就要指向 her 的‘e’

其余同理

（根节点的 fail 指向自己）

构建过程

求 fail[i] 需要用到比 i 深度小的所有点

因此使用 深度优先搜索

当前考虑到了节点 u 他的父亲是 p 通过字符 c 转移而来

即 \(tr[p][c]=u\)

如果 tr[fail[p],c] 存在则让 u 的 fail 指针指向 tr[fail[p],c]

否则一直往上跳（tr[fial[fail[p]],c],tr[fail[fail[fail[p]]],c], ...）实在找不到存在的就到根节点为止

代码

void build()
{
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int v=tr[u][i];
            if(!v) tr[u][i]=tr[nxt[u]][i];
            else
            {
                nxt[v]=tr[nxt[u]][i];
                q.push(v);
            }
        }
    }
}

这里代码跟思路有点小不一样是因为加了个优化

变成了trie图

原本要一直往上跳这回路径压缩

直接一跳到底

板子

例题链接：

AcWing 1282.

Code:

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e4+5,M=1e6+5,S=55;

int tr[N*S][26],cnt[N*S],idx;
queue<int> q;
string str;
int nxt[N*S];
int n;

void insert()
{
    int u=0;
    for(int i=0;str[i];i++)
    {
        int v=str[i]-'a';
        if(!tr[u][v])
            tr[u][v]=++idx;
        u=tr[u][v];
    }
    cnt[u]++;
}

void build()
{
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int v=tr[u][i];
            if(!v) tr[u][i]=tr[nxt[u]][i];
            else
            {
                nxt[v]=tr[nxt[u]][i];
                q.push(v);
            }
        }
    }
}


int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(tr,0,sizeof(tr));
        memset(cnt,0,sizeof(cnt));
        memset(nxt,0,sizeof(nxt));
        idx=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>str;
            insert();
        }
        build();
        cin>>str;
        int ans=0;
        for(int i=0,j=0;str[i];i++)
        {
            int t=str[i]-'a';
            j=tr[j][t];
            int p=j;
            while(p)
            {
                ans+=cnt[p];
                cnt[p]=0;
                p=nxt[p];
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

明人不说暗话，其实AC自动机还有点没搞明白

需要再钻研

赶紧接着学习去了

钻研透彻了就更新修改一下

byebye

参考：AcWing算法提高课 OI Wiki