【学习笔记】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++)" (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];" } query(string x){ ans="0,now=0;" lx="x.length();" now="AC[now].vis[x[i]-'a'];" t="now;t&&AC[t].end!=-1;t=AC[t].fail){" ans+="AC[t].end;" ac[t].end="-1;" return ans; }tat; main(){ ios::sync_with_stdio(false); n; cin>>n;
    for (int i=1;i<=n;i++){ string x; cin>>x;
        TAT.Build(x);
    }
    TAT.Get_Fail();
    string s;
    cin>>s;
    cout<