学步园

题目链接:   hdu 2896

题目大意:   给出N个模式串，最后给出M个主串

                  问有主串出现过哪些模式串，最后输出哪些主串能匹配模式串

解题思路:   AC自动机建立字典树的用w值标记第几个模式串

                  定义k值，匹配时若字典树中的某个结点不等于k且w不为0则记录该点

                  有多个主串需要匹配，所以不需要改变w的值，但可以判断k的值

                  若该失败指针的结点k值已经被匹配过则不需要再次匹配

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 10010
struct snode{
    int w,fail,k;
    int next[128];
}Tree[MAX*6];
int Index,listb[MAX*6],kk,ans[510];
char ch[MAX];

void Insert(int Star,int Tlen,int k)  //建立字典树
{
    int i,S=Star,child;
    for(i=1;i<=Tlen;i++)
    {
        child=ch[i-1];
        if(Tree[S].next[child]==-1)
        {
            if(i==Tlen)
                Tree[Index].w=k;
            Tree[S].next[child]=Index++;
        }
        else
        {
            if(i==Tlen)
                Tree[Tree[S].next[child]].w=k;
        }
        S=Tree[S].next[child];
    }
}

void Build_fail(int Star)     //建立失败指针
{
    int i,tempv,now_fail,e,s;
    e=s=0;
    listb[s++]=Star;
    while(s!=e)
    {
        tempv=listb[e++];
        for(i=0;i<128;i++)
        {
            if(Tree[tempv].next[i]!=-1)
            {
                now_fail=Tree[tempv].fail;
                while(now_fail!=-1)
                {
                    if(Tree[now_fail].next[i]!=-1)
                    {
                        Tree[Tree[tempv].next[i]].fail=Tree[now_fail].next[i];
                        break;
                    }
                    now_fail=Tree[now_fail].fail;
                }
                if(Tree[Tree[tempv].next[i]].fail==-1)  //找不到失败指针，则指向根节点
                    Tree[Tree[tempv].next[i]].fail=0;
                listb[s++]=Tree[tempv].next[i];
            }
        }
    }
}

int Ac_auto(int k,int Tlen)   //BFS匹配
{
    int i,p=0,child,temp,sum=0;
    for(i=1;i<=Tlen;i++)
    {
        child=ch[i-1];
        while(Tree[p].next[child]==-1&&p!=0)
        {
            p=Tree[p].fail;
        }
        p=(Tree[p].next[child]==-1)?0:Tree[p].next[child];  //**
        temp=p;
        while(Tree[temp].w!=-1&&temp!=0&&Tree[temp].k!=k)
        {
            if(Tree[temp].w!=-1&&Tree[temp].k!=k)  //匹配过则不需要再次匹配
            {
                ans[kk++]=Tree[temp].w;
                sum++;
            }
            Tree[temp].k=k;
            temp=Tree[temp].fail;
        }
    }
    return sum;
}

int main()
{
    int i,j,n,m,temp,sumn;
    while(scanf("%d",&n)!=EOF)
    {
        getchar();
        Index=1;
        memset(Tree,-1,sizeof(Tree));  //初始化字典树
        for(i=1;i<=n;i++)
        {
            gets(ch);    //可能有空格输入
            Insert(0,strlen(ch),i);
        }
        scanf("%d",&m);
        getchar();
        Build_fail(0);
        for(i=1,sumn=0;i<=m;i++)
        {
            kk=0;
            gets(ch);    //可能有空格输入
            temp=Ac_auto(i,strlen(ch));  //记录每个主串的匹配次数
            if(temp>=1)
            {
                sumn++;
                sort(ans,ans+kk);    //从小到大输出匹配的模式串的序号
                printf("web %d:",i);
                for(j=0;j<kk;j++)
                    printf(" %d",ans[j]);
                puts("");
            }
        }
        if(sumn>=1)
             printf("total: %d\n",sumn);
    }
    return 0;
}