AC自动机模板

墨蓝 2022-06-05 11:05 218阅读 0赞

昨天晚上来基地看了看AC自动机，大概知道是怎么回事了，敲了一遍kuangbin的模板，还是可以理解的，下面就是对其模板的解析。

/*求目标串中出现了多少个模式串*/
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<iostream>
    
    using namespace std;
    const int maxn = 1e4+10;
    const int maxl = 50+10;
    const int maxm = 1e6+10;
    int n;
    char P[maxl];//模式串
    char T[maxm];//主串
    
    struct Trie{
    
        int nxt[maxn*maxl][26];//Trie树
        int fail[maxn*maxl];//前缀指针，在字符串失配时确定转移的结点
        int end[maxn*maxl];//表示当前位置的结点是不是某个单词的结束结点
        int root, L;//根结点，当前结点
    
        //给Trie树新建一个结点
        int newnode()
        {
            for( int i = 0; i < 26; i++)//新建结点的子节点都为空
                nxt[L][i] = -1;
            end[L++] = 0;//非结束结点
            return L-1;//返回当前结点数
        }
    
        //Trie树初始化
        void init()
        {
            L = 0;//树空
            root = newnode();//新建一个根节点
        }
    
        // 向Trie树中插入模式串
        void insert( char buf[])
        {
            int len = strlen(buf);//模式串长度
            int now = root;//从根节点开始
            for( int i = 0; i < len; i++)
            {
                if( nxt[now][buf[i]-'a'] == -1)//当前字母的结点不存在
                    nxt[now][buf[i]-'a'] = newnode();//新建一个
                now = nxt[now][buf[i]-'a'];//走到当前字母所在结点
            }
            end[now]++;//标记一下串结束的位置
        }
    
        // 建失配表
        void build()
        {
            queue<int> Q;//队列
            fail[root] = root;//根节点的fail指向自己
            //这里保证根节点的子节点的fail都指向根
            for( int i = 0; i < 26; i++)//遍历根节点的26个子节点
            {
                if( nxt[root][i] == -1)//如果子节点不存在
                    nxt[root][i] = root;//????
                else//子节点存在
                {
                    fail[nxt[root][i]] = root;//子节点的fail指向根节点
                    Q.push(nxt[root][i]);//子节点进栈
                }
            }
    
            //对于子节点存在的结点
            while( !Q.empty())
            {
                //取出栈中的结点
                int now = Q.front();
                Q.pop();
                for( int i = 0; i < 26; i++)//遍历当前结点的子节点
                {
                    if( nxt[now][i] == -1)//子节点不存在
                        nxt[now][i] = nxt[fail[now]][i];//????
                    else
                    {
                        fail[nxt[now][i]] = nxt[fail[now]][i];//当前结点的fail沿着父亲的fail走，指向父亲fail的与自己值相同的子节点
                        Q.push(nxt[now][i]);//当前结点进栈
                    }
                }
            }
        }
    
        int query( char buf[])
        {
            int len = strlen(buf);//主串的长度
            int now = root;//指向根节点
            int res = 0;
            for( int i = 0; i < len; i++)//遍历主串
            {
                now = nxt[now][buf[i]-'a'];//当前字符在Trie树中的位置
                int tmp = now;
                while( tmp != root)//==的话为空，前面记录了的，！=代表存在
                {
                    res += end[tmp];//看是否为一个完整的串，是的话就加到res里
                    end[tmp] = 0;//标记已经计算过
                    tmp = fail[tmp];//指向fail指针
                }
            }
            return res;
        }
    };
    
    char buf[1000000];
    
    Trie ac;
    
    int main()
    {
        int T_T;
        scanf("%d",&T_T);
        while( T_T--)
        {
            scanf("%d",&n);
            ac.init();
            for( int i = 0; i < n; i++)
            {
                scanf("%s",P);
                ac.insert(P);
            }
            ac.build();
            scanf("%s",T);
            printf("%d\n",ac.query(T));
        }
    
        return 0;
    }