速通AC自动机

yyrwlj · 2024-01-07 21:12:27 · 个人记录

KMP + Trie

将所有文本串建成一个Trie树。

然后对Trie树构建fail指针（失配指针）

fail指针 = nxt数组

KMP求nxt数组是这样的(注意异或号包裹)：

nxt[0] = nxt[1] = 0;
for (int i=2;i<=n;i++)
{
    int j = nxt[^^ i - 1 ^^];
    while (j && ^^ p[^^ i ^^] ^^ != p[j + 1])
        j = nxt[j];
    if (p[i] == p[j + 1])
        j ++;
    nxt[i] = j;
}

AC自动机构建fail指针是这样的：

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[fail[t]][i];
        else
        {
            fail[p] = tr[fail[t]][i];
            q[++tt] = p;
        }
    }
}

下面是两者相同点（左KMP，右AC自动机）

i - 1 = t

p[i] = i

i = p

翻译一下构建fail

如果不存在这个子节点，那就说明失配了，那就往上跳，直到跳到最终的位置。

存在才需要构建fail，也是往上跳。

也就是区别是让trie还是fail指向上面。

看匹配

for (int i=0,j=0;str[i];i++)
{
    int t = str[i] - 'a';
    j = tr[j][t];
    int p = j;
    while (p && cnt[p] != -1)
    {
        ans += cnt[p];
        cnt[p] = -1;
        p = fail[p];
    }
}

如果这个串包含了前面的串，但是前面的串已经算过就不会继续跳了。

因为前面的串 和前面的串包含的串 在遍历到前面的串的时候 就已经计算完了。

这样这个 while 循环就不会跳很多次了。