ac自动机是一种处理多模式串匹配的字符串算法

基础知识 -> oi wiki ac自动机

常见应用

统计有多少个模式串在文本串中出现过，直接暴力跳$fail$指针,将沿路径上的$end$标记值加上即可，注意为了避免重复匹配，每跳到一个$fail$要将它赋值为$-1$

$fail$树优化：如计算每个模式串在文本串中出现的次数，当数据范围较小（如 $n$ <= $1e3$,其中$n$为模式串的数量）时,可以选择直接暴力跳$fail$指针；但当数据范围较大时，暴力跳$fail$指针会进行很多重复的操作，从而使复杂度大大增加，这时就可以将所有$fail$指针建一棵树，对于每个模式串，统计以它的字符串结尾单词为根的子树和.

原理：

每一个$fail$结点都只对应一个失配字符,故此可以建树

短的模式串在树上的深度一定小于长的模式串，故假设当前模式串已匹配，那么比深度小的在同一棵子树上的模式串必然被匹配过一次了，所以以某一个结点为根的子树和为它所对应的字符串被匹配的次数

代码：

 struct AC_autumaton {
     int tot;
     int fail[N];
     int end[N];
     int trie[N][26];
     int size_fail[N];
     void insert(char *b, int flag) {
         int p = 0, l = strlen(b + 1);
         for (int i = 1; i <= l; i++) {
             int x = b[i] - 'a';
             if (!trie[p][x])
                 trie[p][x] = ++tot;
             p = trie[p][x];
         } end[flag] = p;
     }
     void build_fail() {
         queue <int> que;
         for (int i = 0; i <= 25; i++)
             if (trie[0][i]) que.push(trie[0][i]);
         while (!que.empty()) {
             int p = que.front(); que.pop();
             for (int i = 0; i <= 25; i++) {
                 if (trie[p][i])
                     fail[trie[p][i]] = trie[fail[p]][i],
                         que.push(trie[p][i]);
                 else trie[p][i] = trie[fail[p]][i];
             }
         }
     }
     void query(char *a) {
         int p = 0, l = strlen(a + 1);
         for (int i = 1; i <= l; i++) {
             int x = a[i] - 'a';
             p = trie[p][x];
             size_fail[p]++;        //统计结点出现次数
         }
     }
     struct Edge { int nt, to; } ft[N];
     int hd[N], num;
     void add_fail(int u, int v) {
         ft[++num].nt = hd[u];
         ft[num].to = v;
         hd[u] = num;
     }
     void failtree() {
         for (int i = 1; i <= tot; i++)
             add(fail[i], i);       //按fail指针反向建树
     }
     void dfs_fail(int u) {         //计算子树和
         for (int i = hd[u]; i; i = ft[i].nt) {
             int v = ft[i].to;
             dfs_fail(v);
             size_fail[u] += size_fail[v];
         } return ;
     }
 } ac;