QWQ

AC自动机

首先 你得先了解 KMP 和 Trie

在基于了解了以上两种算法后， 我们考虑构建和使用 AC自动机

AC自动机的本质是一颗 Trie 树，其独特之处在于利用了 KMP 的 Fail 指针

构建

定义 AC自动机

struct AC_aotomaton {
    int son[maxn][26]; // Trie 中结点
    int val[maxn]; // 是否为结束,有多少个单词
    int fail[maxn], last[maxn]; // 失配指针
    int sz;
    void clear() {
        memset(son[0], 0, sizeof(son[0])); sz = 1;
    }
    void clear_p(int x) {
        memset(son[x], 0, sizeof(son[x])); val[x] = 0;
    }
    int cg(char x) {return x - 'a';}
    // Trie树上添加结点
    void insert(char *s) {
        int u = 0;
        int len = strlen(s);
        for(int i = 0;i < len; ++i) {
            int c = cg(s[i]);
            if(!son[u][c]) {
                clear_p(sz); son[u][c] = sz++;
            }
            u = son[u][c];
        }
        val[u]++; // val[u] = (编号) 
    }
    //后面还有别的函数 - 用于求 fail 和匹配
}

构建 fail 指针

fail 指针 指向的结点代表的字符串 是 当前结点字符串的最长后缀

那么我们想一想，当前结点最长的后缀在哪里，假设我们已经求出来当前结点的父亲的 fail 指针，对于当前结点来说，这一定是能找到的除了最后一位的 最长后缀 了

所以，如果 父亲结点的 fail 指针所指向的结点 $p$ 存在与当前结点字符相同的儿子， 那么当前结点的 fail 指针一定是指向结点 $p$ ，否则我们继续寻找指针的指针指向的结点，直到fail指针指向 原点0

于是，考虑如何构建 fail 指针，我们首先把 Trie 树分成一层一层的（姑且形象的定义吧）， 那么对于一个结点的 fail 指针指向的结点， 深度一定小于这个结点的深度， 我们依次放入队列里面，就可以处理出所有结点的 fail 指针了

void getfail() {
    queue<int> q;
    fail[0] = 0;
    int u = 0;
    //Sigma_Size 字符集大小
    for(int i = 0;i < Sigma_Size; ++i) {
        u = son[0][i];
        if(u) {
            q.push(u); fail[u] = 0; last[u] = 0;
        }
    }
    while(!q.empty()) {
        int r = q.front(); q.pop();
        for(int i = 0;i < Sigma_Size; ++i) {
            u = son[r][i];
            if(!u) {
                son[r][i] = son[fail[r]][i]; continue;
            }
            q.push(u);
            int v = fail[r];
            while(v && (!son[v][i])) v = fail[v];
            fail[u] = son[v][i];
            last[u] = val[fail[u]]? fail[u]: last[fail[u]];
        }
    }
}

考虑如何查询

与 KMP 的做法类似，依次对每一个字符进行匹配，如果不能匹配，则转移到 fail 指针所在的结点，直到匹配完成或者 fail 指向原点(0)

int find(char *s) {
    int u = 0, cnt = 0;
    int len = strlen(s);
    for(int i = 0;i < len; ++i) {
        int c = cg(s[i]);
        u = son[u][c];
        int tmp = 0;
        if(val[u]) tmp = u;
        else if(last[u]) tmp = last[u];
        while(tmp) {
            cnt += val[tmp];
            val[tmp] = 0;
            tmp = last[tmp];
        }
    }
    return cnt;
}