AC 自动机

15675808884a · 2026-10-11 11:17:41 · 算法·理论

网上详细讲 AC 自动机的太少了，于是我也来写一篇。

AC 自动机

Q\&A

Q1：AC 自动机是啥？

A1：它是专门用来解决优化 KMP 的多串匹配问题。

Q2：它怎么用？

A2：可以适用于解决多串匹配问题，似乎还可以加上 DP。

Q3：它有什么前置知识？

A3：KMP，Trie，自动机（大致了解即可）。

自动机

又叫做有限状态自动机，其实就是流程图，比如 OI WiKi 的一张图：

这就是一个自动机，可以由一个状态转移到下一个状态，所以可以加上前面说的 DP。

字典树

概念

什么你不了解字典树？

其实我也是零时学的。

它的本质其实是将一堆字符串放到一棵树上面节省空间和时间。

算法流程

OI-WiKi 的图片也是太好用了，可惜 GIF 不多。

建树部分

1. 依次加入这个字符串的字母。
2. 如果发现当前节点没有对应字母的路径新建一个节点对应的字母路径。
3. 如果到头了记录这个节点为结尾。

:::info[模拟例子（注意节点顺序不与上图相符）] 当前例子的节点顺序是 DFS 序。

加入 aa（此例子展示字母全不在树上情况）。

节点一没有 a 的边，创建节点二，连接一条边。

节点二没有 a 的边，创建节点三，连接一条边，记录为结尾。

加入 aba（此例子展示字母部分在树上情况）。

节点一有 a 的边，前往节点二。

节点二没有 b 的边，创建节点四，连接一条边。

节点四没有 a 的边，创建节点五，连接一条边，记录为结尾。

省略一部分重复过程。

加入 cb（此例子展示字母全在树上情况）。

节点一有 c 的边，前往节点八。

节点八有 b 的边，前往节点十三，记录为结尾。

查询

和建树操作类似。

只不过遇到不存在的字母边或结尾没有标记时则没有当前字符串。

这里给出完整操作的代码：

void insert(string &s,int idx){
    int u=0;
    for(char ch:s){
        int c=ch-'a';
        if(!t[u][c])
            t[u][c]=++tot;
        u=t[u][c];
    }
}

void query(){
    int u=0;
    for(char ch:s)
        u=t[u][ch-'a'];
}

KMP

有两种方法，最让人大开眼界的方法在这：

KMP B 站视频

这个视频讲的很详细，我这里具体讲解第二种做法。

相信你已经在上面学会 nxt_i 也就是 \pi_i 是啥意思了，也就是最长相同真相同前后缀 （又臭又长）。

我们对于第二种做法就是暴力匹配，当指针匹配失败时就跳转到 nxt 数组里的位置。

这里给出两种办法的代码。

    cin>>A>>B,n=A.size(),m=B.size(),S=B+"#"+A;
    for(int i=1;i<=n+m+1;i++){
        int len=nxt[i-1];
        while(len!=0&&S[i]!=S[len])
            len=nxt[len-1];
        if(S[i]==S[len])
            nxt[i]=len+1;
    }
    for(int i=m+1;i<=n+m+1;i++)
        if(nxt[i]==m)
            cout<<i-2*m+1<<endl;
    for(int i=0;i<m;i++)
        cout<<nxt[i]<<' ';//No.1

    cin>>A>>B,n=A.size(),m=B.size(),A=' '+A,B=' '+B;
    for(int i=2,j=0;i<=m;i++){
        while(j!=0&&B[i]!=B[j+1])
            j=nxt[j];
        if(B[i]==B[j+1])
            j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j>0&&A[i]!=B[j+1])
            j=nxt[j];
        if(A[i]==B[j+1])
            j++;
        if(j==m)
            cout<<i-m+1<<endl;
    }
    for(int i=1;i<=m;i++)
        cout<<nxt[i]<<' ';//No.2

注意这是模板 KMP 的代码。

AC 自动机

说一句废话：AC 自动机就是字典树的结构加上 KMP 的思想。

我们首先把一堆待匹配的串全加入一棵字典树里面。

然后我们把他加上失配指针 fail_i。

最后按照 KMP 的方法进行匹配。

现在问题来了：

我们怎么去加上失配指针？

我们回看 KMP。

相信你已经在上面学会 nxt_i 也就是 \pi_i 是啥意思了，也就是最长相同真相同前后缀 （又臭又长）。

但是我们真的需要最长相同真相同前后缀吗？

不用，我们要求的是后缀相同的位置。

使用 OI WiKi 的原句：

不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

我们考虑怎么求：

首先根节点的子节点的 fail 指针一定指向根。

然后按照 BFS 的顺序依次求解 fail 指针，这样可以保证 fail 指针指向的节点一定处理过了。

对于两种不同的情况进行处理：

将它儿子的 fail 指针设为它的 fail 指向节点的对应儿子，将它儿子加入队列。

将它儿子设为它的 fail 指向节点的对应儿子。

为何这样是对的？

因为它父亲的 fail 指针一定指向的是它父亲的匹配最佳的位置，所以我们只要把当前节点设为它父亲的 fail 指向节点的对应儿子即可。

可能会有点绕口看这张手绘图：

我们拿字符串 ab 中的 b 举例：

他父亲的 fail 指针是根节点，于是他就指向根节点的 儿子 b。

这下终于把所有东西讲解清楚了。

放一张 OI WiKi 的图片欣赏一下：

代码如下：

现在还没完！！！

我们发现他的时间照样不对于是我们要考虑优化。

不信你看：

:::info[code]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=2e5+1;

ll n,tr[N][26],fail[N],tot,ans[N],orz[N];
vector<int>End[N];
string s,t[N];

void insert(string s,ll idx){
    ll x=0;
    for(auto ch:s){
        ll t=ch-'a';
        if(!tr[x][t])
            tr[x][t]=++tot;
        x=tr[x][t];
    }
    End[x].push_back(idx);
}

void build(){
    queue<ll>q;
    for(ll i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);
    while(!q.empty()){
        ll x=q.front();q.pop();
        for(ll i=0;i<26;i++)
            if(tr[x][i])
                fail[tr[x][i]]=tr[fail[x]][i],q.push(tr[x][i]);
            else
                tr[x][i]=tr[fail[x]][i];
    }
}

void query(){
    ll x=0;
    for(char i:s){
        x=tr[x][i-'a'];
        for(int j=x;j;j=fail[j])
            for(int k:End[j])
                ans[k]++;
    }
}

int main(){
    cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>t[i],insert(t[i],i);
    build(),cin>>s,query();
    for(ll i=1;i<=n;i++)
        cout<<ans[i]<<endl;
}

:::

提交记录 68pts。

于是我们考虑优化。

优化

找到 TLE 的问题：

void query(){
    ll x=0;
    for(char i:s){
        x=tr[x][i-'a'];
        for(int j=x;j;j=fail[j])//看这里
            for(int k:End[j])
                ans[k]++;
    }
}

我们可爱的查询爆炸了。

它被一组数据卡了：

a
aa
aaa
aaaa
...
aaaaa...aaa

Oh No，我无疑是愤怒的。

我们用 fail 构成一棵 fail 树。

那么每走一步，fail 链都可能很长，最坏会退化到：