AC自动机解析

AC自动机用于在主串中，找多个模板串的出现次数。不论是出现次数只记1次，还是几多次，都可。
AC自动机其实就是模板串构成的Trie图加上fail边，有点像kmp里的Next数组，具体解析先放下，没时间，下面是板子。

e对了，最近的东西确实有难度，然额对于稍微难一点的东西，网上的板子都是那种参差不齐的，乱设变量，写的只有自己看得懂，正确性还不绝对保证，变量也不说明都是干啥用的，看的气愤。。
所以，最重要的还是先解释代码中的变量都是干啥用的，啥功能，名字尽可能规范吧。
Trie用来存树(图)，fail[i]表示编号为i的结点指向的结点，val[i]表示编号为i的结点是几个字符串的终点。cnt表示Trie树中已经有多少个结点了。这里再说明一下，Trie树正解应该是数据(字符)都是在边上存的，点的值为编号。

typedef struct AC_Auto{
    int Trie[maxn][26],fail[maxn],val[maxn],cnt;
    void insert(char *s,int len);    //要插入的字符串以及长度
    void build();                    //构建自动机，不需要参数
    int query(char *s,int len);     //根据实际需要写
    void clear();
}AC;
void AC::insert(char *s,int len){
    int root = 0;                   //插入当然是从根节点开始啦
    for (int i=1;i<=len;i++){
        if (!Trie[root][s[i]-'a'+1])  Trie[root][s[i]-'a'+1] = ++cnt;
        root = Trie[root][s[i]-'a'+1];
    }
    val[root]++;                  //终止结点标注一下。
    return;
}
void AC::build(){
    queue<int> q;
    for (int i=1;i<=26;i++)  if (Trie[0][i])  //与根节点直接相连的结点fail边都是直接指向根的，那么入队就行
        q.push(Trie[0][i]);
    while (!q.empty()){
        int temp = q.front();   q.pop();
        for (int i=1;i<=26;i++){
            if (Trie[temp][i]){
                fail[Trie[temp][i]] = Trie[fail[temp]][i];
                q.push(Trie[temp][i]);
            }else{
                Trie[temp][i] = Trie[fail[temp]][i];
            }
        }
    }
    return;
}
int AC::query(char *s,int len){
    int ans = 0;
    int root = 0,temp;
    for (int i=1;i<=len;i++){         //i是扫描主串的，root是扫描Trie图的，与kmp也相似。一个扫描主串，一个扫描模板串。
        root = Trie[root][s[i]-'a'+1];
        temp = root;
        while (root){
            ans += val[root];
            root = fail[root];
        }
    }
    return ans;
}
void AC::clear(){
    cnt = 0;
    memset(Trie,0,sizeof(Trie));
    memset(fail,0,sizeof(fail));
    memset(val,0,sizeof(val));
}

AC自动机不支持在线操作，如果中途插入其他的串，就必须再次build。

emmmm..板子确实长，在注意几点，上面在连fail边的时候，若root的某个子结点存在，那么fail边直接连上root的fail的子结点，然后入队；若不存在，这里优化一下，不存在就不连fail边了，直接把Trie[root][s[i]-'a'+1]赋值为root的fail的子结点，这样，在匹配主串的时候，可以直接当成该子结点存在去匹配，与query()中的root = Trie[root][s[i]-'a'+1];是对上的，这里要再好好想想！

补充：这个板子的query是计算每个模板串出现多次的板子。

最新的板子(topu排序)
洛谷P5357 AC自动机 二次加强版

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2e5+5,maxn2 = 2e6+5;
typedef struct AC_Auto{
    int Trie[maxn][26],fail[maxn],val[maxn],cnt;
    int ans[maxn],cnt2,mp[maxn],in[maxn];
    int times[maxn];                  //表示某个结点出现了多少次
    AC_Auto(){
        cnt = cnt2 = 0;
        memset (times,0,sizeof times);
    }
    void insert(char *s,int len,int flag);    //要插入的字符串以及长度
    void build();                    //构建自动机，不需要参数
    int query(char *s,int len);     //根据实际需要写
    void clear();
    void output();
    void topu();
}AC;
char s[maxn2];
int n,len;
AC a;
int main(){
    scanf ("%d",&a.cnt2);
    for (int i=1;i<=a.cnt2;i++){
        scanf ("%s",s+1);
        a.insert(s,strlen(s+1),i);
    }
    scanf ("%s",s+1);
    a.build();
    a.query(s,strlen(s+1));
    a.topu();
    a.output();
    return 0;
}

void AC::insert(char *s,int len,int flag){
    int root = 0;                   //插入当然是从根节点开始啦
    for (int i=1;i<=len;i++){
        if (!Trie[root][s[i]-'a'+1])  Trie[root][s[i]-'a'+1] = ++cnt;
        root = Trie[root][s[i]-'a'+1];
    }
    val[root]++;                  //终止结点标注一下。
    mp[flag] = root;
    return;
}
void AC::build(){
    queue<int> q;
    for (int i=1;i<=26;i++)  if (Trie[0][i])  //与根节点直接相连的结点fail边都是直接指向根的，那么入队就行
        q.push(Trie[0][i]);
    while (!q.empty()){                       //从队列里面拿出来一个元素temp，然后开始对temp的孩子结点连fail边
        int temp = q.front();   q.pop();
        for (int i=1;i<=26;i++){
            if (Trie[temp][i]){
                fail[Trie[temp][i]] = Trie[fail[temp]][i];
                in[Trie[fail[temp]][i]]++;
                q.push(Trie[temp][i]);
            }else{
                Trie[temp][i] = Trie[fail[temp]][i];
            }
        }
    }
    return;
}
int AC::query(char *s,int len){
    int root = 0,temp;
    for (int i=1;i<=len;i++){         //i是扫描主串的，root是扫描Trie图的，与kmp也相似。一个扫描主串，一个扫描模板串。
        root = Trie[root][s[i]-'a'+1];
        times[root]++;
    }
    return 0;
}
void AC::topu(){
    queue<int> q;
    int temp;
    for (int i=1;i<=cnt;i++)    if (in[i]==0)
        q.push(i);
    while (!q.empty()){
        temp = q.front();   q.pop();
        times[fail[temp]] += times[temp];
        in[fail[temp]]--;
        if (in[fail[temp]]==0)
            q.push(fail[temp]);
    }
    return;
}

void AC::output(){
    for (int i=1;i<=cnt2;i++)
        printf ("%d\n",times[mp[i]]);
    return;
}
void AC::clear(){
    cnt = cnt2 = 0;
    memset(Trie,0,sizeof(Trie));
    memset(fail,0,sizeof(fail));
    memset(val,0,sizeof(val));
    memset(ans,0,sizeof(ans));
    memset(mp,0,sizeof(mp));
}