AC自动机

洛谷P5357模板题
CodeForces 727E Games on a CD补
HDU – 2243
poj2778
nefuoj2027

在写AC自动机相关题目时要注意一下几点 避免浪费时间
1）使用邻接矩阵建图时要注意 将head 清空为-1
2）解决计数问题时mod运算比较费时，少用
3）搞清楚题目要求，在遍历fail树时 ，每个节点 是对他的后缀有影响，还是将它作为后缀的几点有影响，选择bfs还是dfs
4）建边时记得建反向边 即：fail→i
5）必要时通过建立new node函数减少时间复杂度
6）注意内存
7）注意所给串的 符号范围
8）其实有关题目都是相对模板化些，如果在实现过程中出现未知错误，请仔细分析题目
9）可以的话尽量先模拟样例！！！（所有题型）
就酱想起来再补

解决问题：
多模式串的匹配
利用Trie上的有向图建立邻接矩阵的计数问题（从0节点走k次的方案数相当于矩阵自乘k次后∑a【0】【k】的和）用矩阵快速幂加速即可

形式上，AC 自动机基于由若干模式串构成的 Trie 树，并在此之上增加了一些 fail 边；本质上，AC 自动机是一个关于若干模式串的 DFA（确定有限状态自动机），接受且仅接受以某一个模式串作为后缀的字符串。

将多个模式串建立一个Trie树后，假如现在要求模式串在一个文本串中出现的次数
那么我们如果直接暴力在Trie树上匹配的话时间复杂度为O（文本串长度*模式串平均深度）当长度大于1e5时是完全不可以接受的

那么我们利用kmp算法的思想考虑，当到某一节点匹配失效时，是不是也可以不用再从头匹配？利用失败的思想fail指针油然而生
Fail指针即在Trie上的next数组：指向最长相同后缀
如何得到fail指针？
假设P节点之前节点的Fail已经求出，那么P节点的Fail是不是就其父亲节点的Fail对应字符的节点！如果父亲节点的Fail没有对应字符，那我们只需重复找Fail即可
代码中为了降低时间复杂度，我们用了压缩路径的思想，即预处理出每个节点没有对应的字符的Fail
然后我们发现Fail是按层求的，所以我们bfs一下即可

        while(!q.empty()) q.pop();
        for(int i=0;i<26;i++)
            if(trie[0][i]) q.push(trie[0][i]) ;

        while(!q.empty()){
            int f=q.front();q.pop();

            for(int i=0;i<26;i++){
                if(trie[f][i]){
                    fail[trie[f][i]]=trie[fail[f]][i];
                    q.push(trie[f][i]);
                }
                else trie[f][i]=trie[fail[f]][i];//压缩！！
            }
        }
    }

如何进行多模匹配呢？
我们发现其实每一个点只对应一个fail，那么这些fail指针就组成了一颗fail树。
那么我们进行多模匹配的时候其实就是在这颗Fail树上~~（）瞎几把）~~ 跑，那么我们把跑过 的模式串结尾++，然后再在Fail上的每个节点dfs求一下子树和，就能够得到答案了
模式串：
1 22 11 1211 12111
Fail树

void dfs(int x)
{
    int len=vec[x].size();
    for(int i=0;i<len;i++){
        int y=vec[x][i];
        dfs(y);
        dp[x]+=dp[y];
    }
    if(ed[x]) ans[ed[x]]=dp[x];
}
void check(char *s){
    int p=0,len=strlen(s);
    for(int i=0;i<len;i++){
        p=trie[p][s[i]-'a'];
        dp[p]++;
    }
    dfs(0);
}