AC自动机

AC自动机：用于解决多模式串的匹配问题。第一次听到还以为是自动A题的玄学，。，与kmp的思想类似，如果暴力来思考的话，对每一个模式串在原串中进行kmp，时间直接炸裂，这时候就需要ac自动机登场啦。

例题：hdu2222
AC自动机包括三个大部分：建立字典树，求取fail数组，进行匹配；
首先还是初始化及预先声明

int tree[maxm][N],cnt = 0,root,fail[maxm],val[maxm];//val用于标记是单词结尾
    int getnewnode() {
        for(int i = 0;i < N; ++i) tree[cnt][i] = 0;
        fail[cnt] = val[cnt++] = 0;
        return cnt - 1;
    }
    void Initial() {
        cnt = 0;
        root = getnewnode();
    }

一：建立字典树：
这玩意儿我第一次学的时候是拿来找单词的，给单词表，看某个单词是不是在单词表中，有静态的和动态的，这里我写的是静态的.。

void Insert(char *s) {  //把每个模式串插入建立一棵字典树
        int rt = 0,l = strlen(s);
        for(int i = 0;i < l; ++i) {
            int id = s[i] - 'a';
            if(!tree[rt][id]) {
                tree[rt][id] = getnewnode();
            }
            rt = tree[rt][id];
        }
        val[rt]++;
    }

二：求取fail数组;
fail数组的作用和kmp中next数组作用很相似，用于引导在匹配失败的时候到达下一个位置；用word[x] 代表从根到结点x形成的单词，fail[i] = j，代表word[j] 是 word[i] 的最长后缀，模拟下图就明白了:word[4] =“hers”,字典树中存在的最长后是“s”，即word[7];所以fail[4] = 7;

而对于fail数组的求解，采用的是bfs的层次遍历。
假设我们当前需要求取fail[i],设i的“父亲”是x，且已知fail[x]；由此可知，word[fx] 是 word[x]的最长后缀；而fail[i]的作用是当我们匹配到i失配的时候，也就是在字典树中结点 i 下面不存在我们需要的字符的id(设为index)的时候，我们就跳到fail[i]这个结点来看fail[i]是否有index，先决条件就是我们应该保证从根到结点fail[i]之间的字符也可以和原串匹配，也就是word[fail[i]]应该是word[i]的最长后缀(最长 也就利用了最多的信息来减少不必要的匹配)
之前说过，word[fx] 是 word[x]的最长后缀，并且i是x的“儿子”，所以容易得到：fail[i] = tree[fail[x]][index]；

void getfail() {
        queue<int>q; //用于bfs
        while(!q.empty()) q.pop();
        for(int i = 0;i < N; ++i) {
            if(tree[0][i]) q.push(tree[0][i]),fail[tree[0][i]] = 0;
        } 
        while(!q.empty()) {
            int u = q.front();q.pop();
            for(int i = 0;i < N; ++i) {
                if(tree[u][i]) { //如果有i所代表的这个字符 0-25代表'a' ~ 'z';就求解
                    fail[tree[u][i]] = tree[fail[u]][i];
                    q.push(tree[u][i]);
                }else tree[u][i]=tree[fail[u]][i]; //如果没有那么就直接把fail[tree[u][i]]赋值给tree[u][i],实际上这是将trie树基于fail指针添上了没有的边，对AC自动机的优化，
            }
        }
    }

三：匹配
有了之前的铺垫，我们就可以直接遍历一次原串，利用fail指针求出多个模式串的出现次数了

int query(char *s) {
        int rt = 0,len = strlen(s),ans = 0;
        for(int i = 0;i < len; ++i) {
            int id = s[i] - 'a';
            rt = tree[rt][id];
            for(int j = rt;~val[j] && j;j = fail[j]) {
                ans += val[j];
                val[j] = -1;
            } //这个for循环可以也是可以优化掉的
        }
        return ans;
    }

内部的for循环是在计数包含的模式串，比如模式串有abcdefg,cdefg,efg，我们遍历的时候找到了abcdefg，但是事实这里面还有可能有其他的串，通过fail数组的转移，就可以找到cdefg和efg，一直这样递归下去，不断找后缀直到根节点（根代表空的，也就是说已经找不到可能包含的串了）;

完整代码：

//#include<bits/stdc++.h>
#include<queue>
#include <cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define mod (1000000007)
#define middle (l+r)>>1
#define lowbit(x) (x&(-x))
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf_max = 0x3f3f3f3f;
const ll Linf = 9e18;
const int maxn = 1e6 + 10;
const int maxm = 5e5 + 10;
const long double E = 2.7182818;
const double eps=0.0001;
using namespace std;
inline int read()
{
    int f=1,res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { res=res*10+ch-'0' ; ch=getchar(); }
    return f*res;
}
const int N = 30;
struct AC {
    int tree[maxm][N],cnt = 0,root,fail[maxm],val[maxm];
    int getnewnode() {
        for(int i = 0;i < N; ++i) tree[cnt][i] = 0;
        fail[cnt] = val[cnt++] = 0;
        return cnt - 1;
    }
    void Initial() {
        cnt = 0;
        root = getnewnode();
    }
    void Insert(char *s) {
        int rt = 0,l = strlen(s);
        for(int i = 0;i < l; ++i) {
            int id = s[i] - 'a';
            if(!tree[rt][id]) {
                tree[rt][id] = getnewnode();
            }
            rt = tree[rt][id];
        }
        val[rt]++;
    }
    void getfail() {
        queue<int>q;
        while(!q.empty()) q.pop();
        for(int i = 0;i < N; ++i) {
            if(tree[0][i]) q.push(tree[0][i]),fail[tree[0][i]] = 0;
        }
        while(!q.empty()) {
            int u = q.front();q.pop();
            for(int i = 0;i < N; ++i) {
                if(tree[u][i]) {
                    fail[tree[u][i]] = tree[fail[u]][i];
                    q.push(tree[u][i]);
                }else tree[u][i]=tree[fail[u]][i];
            }
        }
    }
    int query(char *s) {
        int rt = 0,len = strlen(s),ans = 0;
        for(int i = 0;i < len; ++i) {
            int id = s[i] - 'a';
            rt = tree[rt][id];
            for(int j = rt;~val[j] && j;j = fail[j]) {
                ans += val[j];
                val[j] = -1;
            }
        }
        return ans;
    }
}ACautoman;
char str[maxn];
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        ACautoman.Initial();
        for(int i = 1;i <= n; ++i) {
            scanf("%s",str);
            ACautoman.Insert(str);
        }
        scanf("%s",str);
        ACautoman.getfail();
        printf("%d\n",ACautoman.query(str));
    }
    return 0;
}