AC自动机学习笔记

AC_Lover · 2025-02-17 08:03:06 · 算法·理论

AC自动机（\texttt{ACAM}）是Trie树和KMP的结合

重点：ne_u=v表示在AC自动机上从根到v表示的字符串和从根到u表示的字符串的一段后缀相等，且长度最长

使用bfs从上向下扫描，可逐层计算出ne数组，而 i\to ne_i 连边构成一棵 \texttt{fail} 树。

核心：（插入和建AC自动机）

int son[N][26],cnt[N],idx; //Trie
int q[N]; //队列
int ne[N]; //AC自动机

void Insert(string s)
{
    int u=0;
    for (int i=0;i<s.length();i++)
    {
        int ch=s[i]-'a';
        if (!son[u][ch]) son[u][ch]=++idx;
        u=son[u][ch];
    }
    cnt[u]++;
}

void build() //建立AC自动机
{
    int hh=0,tt=-1;
    for (int i=0;i<26;i++)
    {
        if (son[0][i])
        {
            q[++tt]=son[0][i];
        }
    }
    while (hh<=tt)
    {
        int u=q[hh++];
        for (int i=0;i<26;i++)
        {
            int v=son[u][i];
            if (!v) son[u][i]=son[ne[u]][i];
            else
            {
                ne[v]=son[ne[u]][i];
                q[++tt]=v;
            }
        }
    }
}

性质：不断跳 ne_i，可以找出所有等于后缀的前缀。