AC自动机学习笔记

一句话概括：

• \(AC\)自动机\(=Trie+Kmp\)

算法复习

\(Trie\)

字典树，顾名思义，是一个字典一样的树，结构非常简单，不再赘述。

code

int son[N][26], cnt[N], idx;

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

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

\(Kmp\)

字符串匹配问题 \(s\)长文本，\(p\)模式串

暴力算法

for (int i = 1; i <= n; i ++ ) // the beginning
{
    for (int j = 1; j <= m; j ++ )
        if (s[i + j - 1] != p[j])
            break;
    if (j > m) success!
}

\(Kmp\)核心思想：一次匹配失败后，直接跳往最近的可能成功位置继续匹配。

\(next[i]\) 在模式串\(p\)中，以\(p[i]\)结尾的后缀，能够匹配的从一开始的非平凡前缀的最大长度。

code

// the index of s,p begin with 1

void get_ne()
{
    next[0] = next[1] = 0;
    for (int i = 2, j = 0; i <= m; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
}

void kmp()
{
    for (int i = 1, j = 0; i <= n; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m)
        {
            j = ne[j];
            success!
        }
    }
}

简单来说，\(AC\)自动机就是\(Trie\)树存每个模式串，然后考虑每个模式串的结尾字符\(ch\)，有一个后缀\(suf\)考虑如何去求\(fail\)失配指针（最长后缀，和\(Kmp\)中的\(next\)数组类似）。

可以利用\(BFS\)进行\(fail\)失配指针的求解。由于同时需要记录是否重复，所以我们在多次搜索时会新增一个 \(copy\) 数组。

code

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

int tr[N * S][26], cnt[N * S];
char str[M];
int q[N * S], ne[B * S];

void init()
{
    memset(tr, 0, sizeof tr);
    memset(cnt, 0, sizeof cnt);
    memset(ne, 0, sizeof ne);
    idx = 0;
}

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

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}