HDU 2896 病毒侵袭（AC自动机）

小灰灰 2021-01-12 03:01 594阅读 0赞

题意：求m个网站出现过的病毒串并按id从小到大输出。最后一行输出含有病毒的网站数量。

思路：AC自动机模板题，注意可见字符的范围是128...这题空间卡的比较严。。

代码:

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int maxw = 130;
    const int maxn = 210;
    const int time = 505;
    const int maxs = 10010;
    
    struct DFAAC{
        int tire[maxn*time][maxw];
        int fail[maxn*time];
        int tag[maxn*time];
        bool vis[time];
        int P , root , tail , stat;
        int New(){
            tail = stat = 0;
            for(int i=0;i<maxw;i++) tire[P][i] = -1;tag[P] = 0;
            return P++;
        }
        void init(){
            P=0;root =New();
        }
        void Insert(char ch[] , int id){
            int now = root;
            for(int i=0;ch[i];i++){
                if(tire[now][ch[i]]==-1) tire[now][ch[i]] = New();
                now = tire[now][ch[i]];
            }
            tag[now] = id;
        }
        void built()
        {
            queue<int>Q;
            fail[root] = root;
            for(int i = 0 ; i < maxw;i++){
                if(tire[root][i]!=-1){
                    Q.push(tire[root][i]);
                    fail[tire[root][i]] = root;
                }
                else tire[root][i] = root;
            }
            while(!Q.empty()){
                int u = Q.front();Q.pop();
                for(int i=0;i < maxw;i++){
                    if(tire[u][i]!=-1){
                        fail[tire[u][i]] = tire[fail[u]][i];
                        Q.push(tire[u][i]);
                    }
                    else tire[u][i] = tire[fail[u]][i];
                }
            }
        }
        void Match(char ch[]){
            memset(vis,0,sizeof(vis));
    
            int now = root;
            for(int i=0;ch[i];i++){
                now = tire[now][ch[i]];
                int tmp = now;
                while(tmp!=root){
                    if(tag[tmp]) vis[tag[tmp]] = 1;
                    tmp = fail[tmp];
                }
            }
        }
    
    };
    DFAAC ac;
    char ch[maxs];
    int n , m;
    vector<int>ans[maxs];
    int main()
    {
        while(~scanf("%d",&n)){
            ac.init();
            for(int i=1;i<=n;i++){
                scanf("%s",ch);
                ac.Insert(ch , i);
            }
            ac.built();
            scanf("%d",&m);
            for(int i=1;i<=m;i++) ans[i].clear();
            for(int i=1;i<=m;i++){
                memset(ac.vis,0,sizeof(ac.vis));
                scanf("%s",ch);
                ac.Match(ch);
                for(int j=1;j<=n;j++){
                    if(ac.vis[j]){
                        ans[i].push_back(j);
                    }
                }
            }
            int tot = 0;
            for(int i=1;i<=m;i++){
                int sz = ans[i].size();
                if(sz!=0)printf("web %d:",i),tot++;
                for(int j = 0 ; j < sz;j++){
                    printf(" %d",ans[i][j]);
                }
                if(sz!=0)
                printf("\n");
            }
            printf("total: %d\n",tot);
        }
    }