AC自动机

一、定义

AC自动机用于多模式匹配，类似树上 kmp 算法。但是 kmp 只有一个模式串，AC 自动机有多个模式串，可以用多个模式串匹配要查询的字符串。

二、原理

AC自动机以Trie树为基础，结合KMP思想建立。

构造模式串的Trie树
对Trie树上的所有节点构造失配指针fail（类似kmp中的next数组）

失配指针

多模式串匹配时，假设 $pre1, pre2$ ，如果原串在 $pre1$ 匹配失败，则会跳到最长的一个 $pre1$ 的后缀处继续匹配。fail指针指向失配串的最长后缀。

fail指针与next数组的异同点

共同点：两者同样是在失配的时候用于跳转的指针。
不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。

构造失配指针

考虑字典树中当前的结点 $u$ ， $u$ 的父节点是 $p$ ， $p$ 通过字符 $c$ 的边指向 $u$ ，即 $trie[p][c] = u$ 。假设深度小于 $u$ 的所有节点的 fail 指针都已经求出来了。那么现在构造 $u$ 的失配指针。

如果 $trie[fail[p]][c]$ 存在（也就是父节点的失配指针后面加一个字符 $c$ ），那么让 $u$ 的 fail 指针指向 $trie[fail[p]][c]$ 。相当于在 $p$ 和 $fail[p]$ 后面加了一个字符 $c$ ，分别对应 $u$ 和 $fail[u]$ 。
如果 $trie[fail[p]][c]$ 不存在，则继续向上找 $trie[fail[fail[p]]][c]$ ，贪心的找最长后缀。一直跳到根节点。
如果根节点也不存在，那么就让 $fail[u]$ 指向根节点。

如此就完成了 $fail[u]$ 的构建。

假设 $u = 6$ ，先找父节点 $5$ ， $5$ 的fail指针指向 $10$

$10$ 没有 $s$ 边，继续找 $10$ 的fail， $10$ 的fail指向 $0$

$0$ 存在 $s$ 边，所以 $6$ 的fail指向 $7$

构造的代码如下所示。

void build() {
  for (int i = 0; i < 26; i++)
  {
      if (tr[0][i]) q.push(tr[0][i]);
  }
  while (q.size()) 
  {
    int u = q.front();
    q.pop();
    for (int 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];
    }
  }
}

构建时使用 $BFS$ 遍历，一次求队列内结点的 fail 指针。注意不将根节点入队，而是将根节点的子节点入队（如果将根节点 $root$ 入队，会将根节点的儿子 $u$ 的fail指针设置为 $fail[u] = tr[root][c] = u$ ，设置成了自身。因此应该把根节点的孩子入队，同时把孩子的fail指针标记为 $0$ ，可能已经被初始化过了，不用标记）。

然后每次取出队首节点 $u$ ，遍历字符集：

如果 $tr[u][i]$ 存在，将 $tr[u][i]$ 的 fail 指针赋值为 $tr[fail[u]][i]$ 。（本来应该使用while循环，不停向前跳，但是这里通过路径压缩简化了代码，通过else语句代码修改字典树结构，将不存在的字典树的状态链接到了失配指针对应的状态，相当于转移了一个模式串。）这样就得到了自动机。类似编译原理中的自动机。
如果 $tr[u][i]$ 不存在，则令 $tr[u][i]$ 指向 $tr[fail[u]][i]$ ，路径压缩

匹配查询

匹配查询的代码如下所示：

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

每次在字典图上走一个节点，然后访问fail指针，找能够匹配的所有的模式串，加到答案上，然后清零，将该模式串标记为已经统计过了。

复杂度分析：

时间复杂度：定义 $|s_i|$ 是模板串的长度， $|S|$ 是文本串的长度， $|\sum|$ 是字符集的大小（常数，一般为 26）。如果连了 trie 图，时间复杂度就是 $O(\sum|s_i|+n|\Sigma|+|S|)$ ，其中 $n$ 是 AC 自动机中结点的数目，并且最大可以达到 $O(\sum|s_i|)$ 。如果不连 trie 图，并且在构建 fail 指针的时候避免遍历到空儿子，时间复杂度就是 $O(\sum|s_i|+|S|)$ 。

例题P3808 【模板】AC 自动机（简单版）

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
struct ACTrie
{
    const static int M = 26;
    const static int maxn = 1e6 + 10;
    int next[maxn][M] = {}, fail[maxn] = {}, cnt = 0;
    int exist[maxn] = {};
    queue<int> q;
    void insert(char *s)
    {
        int now = 0, len = strlen(s);
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            if (!next[now][c])
                next[now][c] = ++cnt;
            now = next[now][c];
        }
        exist[now]++;
    }

    void build()
    {

        for (int i = 0; i < M; ++i)
        {
            if (next[0][i])
            {
                fail[next[0][i]] = 0;
                q.push(next[0][i]);
            }
        }
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < M; ++i)
            {
                if (next[u][i])
                {
                    fail[next[u][i]] = next[fail[u]][i];
                    q.push(next[u][i]);
                }
                else
                    next[u][i] = next[fail[u]][i];
            }
        }
    }

    int query(char *s)
    {
        int now = 0, len = strlen(s), ans = 0;
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            now = next[now][c];
            for (int j = now; j && exist[j] != 0; j = fail[j])
            {
                ans += exist[j];
                exist[j] = 0;
            }
        }
        return ans;
    }
};
char a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    ACTrie trie;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        trie.insert(a);
    }
    trie.build();
    cin >> a;
    cout << trie.query(a) << endl;
    return 0;
}

使用node版

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
struct Node
{
    const static int M = 26;
    int next[M];
    int exist;
    int fail;
} trie[maxn];
int cnt = 0;
void insert(char *s)
{
    int now = 0, len = strlen(s);
    for (int i = 0; i < len; ++i)
    {
        int c = s[i] - 'a';
        if (!trie[now].next[c])
            trie[now].next[c] = ++cnt;
        now = trie[now].next[c];
    }
    trie[now].exist++;
}
queue<int> q;
void build()
{
    for (int i = 0; i < 26; ++i)
    {
        int child = trie[0].next[i];
        if (child)
        {
            trie[child].fail = 0;
            q.push(child);
        }
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int child = trie[u].next[i];
            if (child)
            {
                trie[child].fail = trie[trie[u].fail].next[i];
                q.push(child);
            }
            else
                trie[u].next[i] = trie[trie[u].fail].next[i];
        }
    }
}

int query(char *s)
{
    int u = 0, len = strlen(s), ans = 0;
    for (int i = 0; i < len; ++i)
    {
        u = trie[u].next[s[i] - 'a'];
        for (int j = u; j && trie[j].exist; j = trie[j].fail)
        {
            ans += trie[j].exist;
            trie[j].exist = 0;
        }
    }
    return ans;
}
char a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        insert(a);
    }
    build();
    cin >> a;
    cout << query(a) << endl;
    return 0;
}

例题P3796 【模板】AC 自动机（加强版）