AC日记——病毒侵袭 hdu 2896

2896

思路：

　　好题；

代码：

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

#define maxn 100001

int ne[][],tag[],fail[],n,tot,m,ans;

char ch[maxn];

bool vis[],out,sc[];

queue<int>que;

int main()

{

    int i,j,len,now,temp;

    scanf("%d",&n);

    tot=,ans=;getchar();

    for(i=;i<=n;i++)

    {

        gets(ch);

        len=strlen(ch);

        now=;

        for(j=;j<len;j++)

        {

            if(!ne[now][ch[j]]) ne[now][ch[j]]=++tot;

            now=ne[now][ch[j]];

        }

        tag[now]=i;

    }

    que.push();

    while(!que.empty())

    {

        now=que.front();que.pop();

        for(i=;i<;i++)

        {

            if(!ne[now][i]) continue;

            if(now==) fail[ne[now][i]]=now;

            else

            {

                temp=fail[now];

                while(temp)

                {

                    if(ne[temp][i])

                    {

                        fail[ne[now][i]]=ne[temp][i];

                        break;

                    }

                    temp=fail[temp];

                }

                if(!temp) fail[ne[now][i]]=;

            }

            que.push(ne[now][i]);

        }

    }

    scanf("%d",&m);getchar();

    for(i=;i<=m;i++)

    {

        out=false;

        for(j=;j<=n;j++) sc[j]=false;

        for(j=;j<;j++) vis[j]=false;

        gets(ch);

        len=strlen(ch),now=;

        for(j=;j<len;j++)

        {

            if(ne[now][ch[j]]) now=ne[now][ch[j]];

            else

            {

                temp=fail[now];

                while(temp)

                {

                    if(ne[temp][ch[j]])

                    {

                        now=ne[temp][ch[j]];

                        break;

                    }

                    temp=fail[temp];

                }

                if(!temp) now=;

            }

            temp=now;

            while(!vis[temp])

            {

                vis[temp]=true;

                if(!sc[tag[temp]]&&tag[temp]) out=true,sc[tag[temp]]=true;

                temp=fail[temp];

            }

        }

        if(out)

        {

            printf("web %d:",i);

               for(j=;j<=n;j++) if(sc[j]) printf(" %d",j);

              printf("\n"),ans++;

        }

    }

    printf("total: %d\n",ans);

    return ;

}