【学习笔记】AC 自动机

听老师说 AC 自动机不算自动机啊，因为 Wikipedia 上的说法也是 $Aho–Corasick algorithm$ 而不是 $Aho–Corasick Automaton$.

然鹅既然大家都这么叫了我标题也就这么起喽 or2

原理

和往常一样，先坑着。。。

例题

模式串匹配

先上个洛谷模板的代码。题目很裸（毕竟是简单模板），给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

代码

#include 
#define ll long long
#define maxn 1000010
using namespace std;
struct Node{
    int vis[26];
    int fail,end;
};
struct ACA{
    Node AC[maxn];
    int cnt;
    void Build(string x){
        int now=0,lx=x.length();
        for (int i=0;iq;
        for (int i=0;i<26;i++)
            if (AC[0].vis[i]) 
                AC[AC[0].vis[i]].fail=0,
                q.push(AC[0].vis[i]);
        while(!q.empty()){
            int hq=q.front();
            q.pop();
            for (int i=0;i<26;i++)
                if (AC[hq].vis[i])
                    AC[AC[hq].vis[i]].fail=AC[AC[hq].fail].vis[i],
                    q.push(AC[hq].vis[i]);
                else AC[hq].vis[i]=AC[AC[hq].fail].vis[i];
        }
    }
    int Query(string x){
        int ans=0,now=0;
        int lx=x.length();
        for (int i=0;i>n;
    for (int i=1;i<=n;i++){
        string x;
        cin>>x;
        TAT.Build(x);
    }
    TAT.Get_Fail();
    string s;
    cin>>s;
    cout<