模板及讲解

AC自动机是什么

由Aho-Corasick发明的一种多模式串匹配算法，基本思想为在Trie上KMP。

AC自动机解决什么问题

AC自动机解决多模板匹配文本串问题。复杂度$O(\sum len_i \times$ 字符集大小$)$
($\sum len_i$ 即为所有模式串总长(可能比Trie树大小大)，字符集大小为出现的字符种类个数)

AC自动机的实现

例题：Hdu 2222

题意：第一行输入测试数据的组数，然后输入一个整数n，接下来的n行每行输入一个单词，最后输入一个字符串，问在这个字符串中有多少个单词出现过。

原理 (求失配函数)

AC自动机是在Trie树上加上失配边完成的。如图所示为加入hers, hehe, he模式串的情况。

Markdown

可以看出在5到6(已经匹配heh如果)失配，则回到1。6失配同理。
与KMP算法有类似之处，所以AC自动机的失配函数与KMP相似。
AC自动机失配函数由BFS可以求得。具体可以看下列代码

代码实现

程序主要函数：$insert$(插入单词), $find$(进行匹配), $getFail$(求失配函数)
其中$insert$(插入单词)为Trie树部分。

坑点：
1、 sz初始化为500000不是500000 + 5
2、ch从0开始清空

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, sz = 500000, ch[500000 + 5][30], val[500000 + 5], tms[500000 + 5], lst[500000 + 5], f[500000 + 5], used[10000 + 5];
//n，节点时间戳，字典树数组，是否是单词, 单词出现个数，上一个单词位置(后缀链接)，失配函数，该单词是否记录过 
char s[1000000 + 5];
int ans;//答案 
void g(int u) {//统计 
    if (!used[val[u]] && u) ans += tms[u], used[val[u]] = true, g(lst[u]);
    //如果没有记录过并且有单词(u!=0), 则加上数量继续向下递归处理 
}
void insert(char *s, int u, int ith, int a, int len) {//插入一个单词(递归更新，不建议)
    int c = s[a] - 'a';
    if (ch[u][c] == 0) ch[u][c] = ++sz;//新建节点 
    if (a == len - 1) val[ch[u][c]] = ith, tms[ch[u][c]]++; else insert(s, ch[u][c], ith, a + 1, len);
    //如果是最后一个要加是单词的标记，并且注意重复的单词 
}
void insert(char *s, int ith) {//插入一个单词(迭代更新，建议)
    int now = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (!ch[now][c]) ch[now][c] = ++sz;//新建节点
        now = ch[now][c];
        if (i == len - 1) val[now] = ith, tms[now]++;
        //如果是最后一个要加是单词的标记，并且注意重复的单词 
    }
}
void find(char *T) {//用字符串T当做文本串找模式串 
    int len = strlen(T), j = 0;//从0开始 
    for (int i = 0; i < len; i++) {
        int c = T[i] - 'a';
        j = ch[j][c];
        if (val[j]) g(j); else if (lst[j]) g(lst[j]);//如果当前位置有单词或者有上一个单词(不会多余, 例子1看代码末行)则处理 
    }
}
void getFail() {//得到失配函数 
    queue<int> q;
    f[0] = 0;//初始化开始点的失配函数为0 
    for (int c = 0; c < 26; c++) {//初始化所以与0相连的点 
        int v = ch[0][c];
        if (v) q.push(v), f[v] = 0, lst[v] = 0;
    }
    while (!q.empty()) {//bfs更新 
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (!v) {ch[u][c] = ch[f[u]][c]; continue;}    //Trie上没有这条边 
            q.push(v);
            int j = f[u]; while (j && !ch[j][c]) j = f[j];//沿着失配边走 
            f[v] = ch[j][c], lst[v] = (val[f[v]]) ? (f[v]) : (lst[f[v]]); 
            //得到失配函数值，求出lst值 
        }
    }
}
void clean() {//清除 
    for (int i = 0; i <= sz; i++) {
        for (int j = 0; j < 26; j++) ch[i][j] = 0;
        f[i] = lst[i] = val[i] = tms[i] = 0;
    }
    for (int i = 0; i <= n; i++) used[i] = false;
    sz = 0;
}
void solve() {
    scanf("%d", &n);
    clean();
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        //insert(s, 0, i, 0, strlen(s));//递归 
        insert(s, i);//迭代 
    }
    scanf("%s", s);
    getFail(), ans = 0, find(s);
    printf("%d\n", ans);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}
/*
例子1： 
1
2
errd
rr
errd
如果不执行该语句，rr则不能被算入 
*/