HDU - 2896病毒侵袭(AC自动机)

墨蓝 2022-06-04 00:39 253阅读 0赞

[点我看题][Link 1]

题意：给n个模式串，m个主串，问哪些模式串在主串中出现过，输出出现过的模式串的次序。

分析：AC自动机模板题，开一个used数组标记第i个模式串是否在主串中出现过，且每个串的结果直接在query函数中输出。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<set>
    #include<queue>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    const int maxn = 5e2+10;
    const int maxp = 2e2+10;
    const int maxt = 1e4+10;
    int n,m;
    char P[maxp];
    char T[maxt];
    int cnt;
    set<int> ans;
    
    struct Aho{
    
        int tt[maxn*maxp][128];
        int fail[maxn*maxp];
        int endc[maxn*maxp];
        int root, L;
    
        int newnode()
        {
            for( int i = 0; i < 128; i++)
                tt[L][i] = -1;
            endc[L++] = -1;
            return L-1;
        }
    
        void init()
        {
            L = 0;
            root = newnode();
        }
    
        void insert( char buf[], int id)
        {
            int len = strlen(buf);
            int now = root;
            for( int i = 0; i < len; i++)
            {
                if( tt[now][buf[i]] == -1)
                    tt[now][buf[i]] = newnode();
                now = tt[now][buf[i]];
            }
            endc[now] = id;
        }
    
        void build()
        {
            queue<int> Q;
            fail[root] = root;
            for( int i = 0; i < 128; i++)
            {
                if( tt[root][i] == -1)
                    tt[root][i] = root;
                else
                {
                    fail[tt[root][i]] = root;
                    Q.push(tt[root][i]);
                }
            }
    
            while( !Q.empty())
            {
                int now = Q.front();
                Q.pop();
                for( int i = 0; i < 128; i++)
                {
                    if( tt[now][i] == -1)
                        tt[now][i] = tt[fail[now]][i];
                    else
                    {
                        fail[tt[now][i]] = tt[fail[now]][i];
                        Q.push(tt[now][i]);
                    }
                }
            }
        }
    
        bool used[510];
        bool query( char buf[], int id)
        {
            int len = strlen(buf);
            int now = root;
            memset(used,false,sizeof(used));
            bool flag = false;
            for( int i = 0; i < len; i++)
            {
                now = tt[now][buf[i]];
                int tmp = now;
                while( tmp != root)
                {
                    if( endc[tmp] != -1)
                    {
                        used[endc[tmp]] = true;
                        flag = true;
                    }
                    tmp = fail[tmp];
                }
            }
    
            if( !flag)
                return false;
            printf("web %d:",id);
            for( int i = 1; i <= n; i++)
                if( used[i])
                    printf(" %d",i);
            puts("");
            return true;
        }
    
    };
    Aho ac;
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            ac.init();
            for( int i = 1; i <= n; i++)
            {
                scanf("%s",P);
                ac.insert(P,i);
            }
            ac.build();
    
            scanf("%d",&m);
            cnt = 0;
            for( int i = 1; i <= m; i++)
            {
                scanf("%s",T);
                if( ac.query(T,i))
                    cnt++;
            }
            printf("total: %d\n",cnt);
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2896