【HDU 2896 病毒侵袭】 AC自动机

时间:2022-05-04 06:25:41

HDU2896
题意就是给你一些病毒网站的关键字,再给你一些网站链接,问每个网站出现过哪些病毒网站关键字
我们只需要用病毒网站关键字构建出AC自动机,之后对每个网站开一个set存储与见过的病毒网站关键字下标就可以了,注意本题字符为ASCII码可见字符,所以tree[][]数组第二维要开到128
HDU2896代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<set>
#include<queue>
#include<stdlib.h>
using namespace std;
const int maxn = 5e5+5;
struct ACTrie
{
    int tree[maxn][128],fail[maxn],end_[maxn];
    int root,cnt,num;
    set<int> s;
    int newnode()
    {
        for(int i=0;i<128;i++)
            tree[cnt][i]=-1;
        end_[cnt]=0;
        return cnt++;
    }
    void init()
    {
        cnt=0;
        num=0;
        root=newnode();
    }
    void insert_(char str[])
    {
        int len=strlen(str);
        int pos=root;
        for(int i=0;i<len;i++)
        {
            int id=str[i];
            if(tree[pos][id]==-1) tree[pos][id]=newnode();
            pos=tree[pos][id];
        }
        end_[pos]=++num;
    }
    void build()
    {
        queue<int> que;
        fail[root]=root;
        for(int i=0;i<128;i++)
        {
            if(tree[root][i]==-1) tree[root][i]=root;
            else
            {
                fail[tree[root][i]]=root;
                que.push(tree[root][i]);
            }
        }
        while(!que.empty())
        {
            int now=que.front();
            que.pop();
            for(int i=0;i<128;i++)
            {
                if(tree[now][i]==-1)
                    tree[now][i]=tree[fail[now]][i];
                else
                {
                    fail[tree[now][i]]=tree[fail[now]][i];
                    que.push(tree[now][i]);
                }
            }
        }
    }
    void query(char str[])
    {
        s.clear();
        int len=strlen(str);
        int now=root;
        int res=0;
        for(int i=0;i<len;i++)
        {
            now=tree[now][str[i]];
            int temp=now;
            while(temp!=root)//对每一个前缀串递归统计是否有后缀是病毒串
            {
                if(end_[temp]!=0) s.insert(end_[temp]);
                temp=fail[temp];
            }
        }
        return ;
    }
};
ACTrie ac;
char str[10005];
int main()
{
    int n,m;
    int flag=0;
    scanf("%d",&n);
    ac.init();
    while(n--)
    {
        scanf("%s",str);
        ac.insert_(str);
    }
    ac.build();
    scanf("%d",&m);
    int cnt=0;
    int ans=0;
    while(m--)
    {
        scanf("%s",str);
        ac.query(str);
        cnt++;
        if(ac.s.size()!=0)
        {
            ans++;
            set<int>::iterator it;
            printf("web %d:",cnt);
            for(it=ac.s.begin();it!=ac.s.end();++it)
            {
                printf(" %d",*it);
            }
            printf("\n");
        }
    }
    printf("total: %d\n",ans);
   return 0;
}