病毒侵袭

/*        ┆ ┏┓　　　┏┓ ┆        ┆┏┛┻━━━━━━┛┻┓  ┆        ┆┃　　　　　 ┃ ┆        ┆┃　    ━　　┃ ┆        ┆┃　┳┛　┗┳  ┃ ┆        ┆┃　　　　　 ┃ ┆        ┆┃　　　┻　　┃ ┆        ┆┗━┓　  　┏━┛ ┆        ┆　┃　  　┃　　┆　　　　　　        ┆　┃　  　┗━━━┓ ┆        ┆　┃　 AC代马  ┣┓┆        ┆　┃　        ┏┛┆        ┆　┗┓┓ ┏━┳┓ ┏┛ ┆        ┆　　┃┫┫　┃┫┫ ┆        ┆　　┗┻┛　┗┻┛ ┆*//*用gets就超内存*/#include<queue>#include<set>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int maxnode=100000+100;const int sigma_size=128;struct AC_Automata{    int ch[maxnode][sigma_size];    int val[maxnode];   /// 每个字符串的结尾结点都有一个非0的val    int f[maxnode];     /// fail函数    int last[maxnode];  /// last[i]=j表j节点表示的单词是i节点单词的后缀，且j节点是单词节点    int sz;    ///初始化0号根节点的相关信息    inline void init()    {        sz=1;        memset(ch[0],0,sizeof(ch[0]));        val[0]=f[0]=last[0]=0;    }    ///Insert负责构造ch与val数组    ///插入字符串,v必须非0表示一个单词节点    inline void Insert(char *s,int v)    {        int n=strlen(s),u=0;        for(int i=0; i<n; i++)        {            int id=s[i];            if(ch[u][id]==0)            {                ch[u][id]=sz;                memset(ch[sz],0,sizeof(ch[sz]));                val[sz++]=0;            }            u=ch[u][id];        }        val[u]=v;    }    ///递归打印与结点i后缀相同的前缀节点编号    ///进入此函数前需保证val[i]>0    inline void print(int i,set<int>&st)    {        if(val[i])        {            //printf("%d\n",val[i]);            if(st.find(i)==st.end())st.insert(val[i]);            print(last[i],st);        }    }    /// 在s中找出 出现了哪几个模板单词    inline void Find(char *s,set<int>&st)    {        int n=strlen(s),j=0;        for(int i=0; i<n; i++)        {            int id=s[i];            while(j && ch[j][id]==0) j=f[j];            j=ch[j][id];            if(val[j]) print(j,st);            else if(last[j]) print(last[j],st);        }    }    ///getFail函数负责构造f和last数组    inline void getFail()    {        queue<int> q;        last[0]=f[0]=0;        for(int i=0; i<sigma_size; i++)        {            int u=ch[0][i];            if(u)            {                f[u]=last[u]=0;                q.push(u);            }        }        while(!q.empty())/// 按BFS顺序计算fail        {            int r=q.front(); q.pop();            for(int i=0; i<sigma_size; i++)            {                int u=ch[r][i];                if(u==0)continue;                q.push(u);                int v=f[r];                while(v && ch[v][i]==0) v=f[v];                f[u]= ch[v][i];                last[u] =  val[f[u]]?f[u]:last[f[u]];            }        }    }};AC_Automata ac;char word[200+10];char text[10000+10];set<int>::iterator it;int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    int n,m;    while(scanf("%d",&n)==1&&n)    {        ac.init();        getchar();        for(int i=1;i<=n;i++)        {            scanf("%s",word);            //cout<<word[i]<<" ";            ac.Insert(word,i);            //cout<<word<<endl;        }        //cout<<endl;        ac.getFail();        scanf("%d",&m);        getchar();        int cur=0;        for(int i=1;i<=m;i++)        {            scanf("%s",text);            set<int>s;            ac.Find(text,s);            if(s.size()>0)            {                cur++;                printf("web %d:",i);                for(it=s.begin();it!=s.end();it++)                    printf(" %d",*it);                printf("\n");            }        }        printf("total: %d\n",cur);    }    return 0;}