ouuan 的博客

ouuan 的博客

题解 P5357 【【模板】AC自动机(二次加强版)】

posted on 2019-05-07 18:09:43 | under 题解 |

形式上,AC 自动机基于由若干模式串构成的 Trie 树,并在此之上增加了一些 fail 边;本质上,AC 自动机是一个关于若干模式串的 DFA(确定有限状态自动机),接受且仅接受以某一个模式串作为后缀的字符串。

并且,与一般自动机不同的,AC 自动机还有 关于某个模式串的接受状态(我自己起的名字..),也就是与某个模式串匹配(以某个模式串为后缀)的那些状态,即某个模式串在 Trie 树上的终止节点在 fail 树上的整个子树。

这段话我先放上来,因为我相信绝大部分人学了 AC 自动机之后甚至不知道 AC 自动机是什么,而只知道它有什么用。

这篇题解假定你会 AC 自动机,如果不会的话,可以看我写的教程

然后的话,很多人用 AC 自动机进行多模匹配时都会暴力跳 fail 边,但这样做复杂度是错误的,可以被类似于 aaaaa……aaaaa 这样的串卡掉。

正确的做法是建出 fail 树,记录自动机上的每个状态被匹配了几次,最后求出每个模式串在 Trie 上的终止节点在 fail 树上的子树总匹配次数就可以了。

参考代码:

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 200010;
const int T = 200010;
const int S = 2000010;

void dfs(int u);
void add(int u, int v);

char s[S];
queue<int> q;
int head[T], nxt[T], to[T], cnt;
int n, tr[T][26], fail[T], tot = 1, match[N], siz[T];

int main()
{
    int i, j, u;

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)
    {
        scanf("%s", s);
        for (u = 1, j = 0; s[j]; ++j)
        {
            int c = s[j] - 'a';
            if (!tr[u][c]) tr[u][c] = ++tot;
            u = tr[u][c];
        }
        match[i] = u; // 记录每个模式串在 Trie 树上的终止节点
    }

    for (i = 0; i < 26; ++i) tr[0][i] = 1; // 一种比较与众不同(个人认为比较正确)的 AC 自动机建法,详见上文提到的我写的博客

    q.push(1);

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

    scanf("%s", s);

    for (u = 1, i = 0; s[i]; ++i)
    {
        u = tr[u][s[i] - 'a'];
        ++siz[u]; // 记录匹配次数
    }

    for (i = 2; i <= tot; ++i) add(fail[i], i); // 建 fail 树

    dfs(1); // 统计子树和

    for (i = 1; i <= n; ++i) printf("%d\n", siz[match[i]]);

    return 0;
}

void dfs(int u)
{
    int i, v;
    for (i = head[u]; i; i = nxt[i])
    {
        v = to[i];
        dfs(v);
        siz[u] += siz[v];
    }
}

void add(int u, int v)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}