学步园

题目链接:   hdu 3065

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

                  问有模式串在主串中出现的次数

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

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

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

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

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 52
struct snode{
    int w,fail;
    int next[26];
}Tree[MAX*1010];
int Index,visit[1010],listb[1000001];
char ch[2000010],ch1[1010][MAX];

void Insert(int Star,int Tlen,int k)   //建立字典树
{
    int i,S=Star,child;
    for(i=1;i<=Tlen;i++)
    {
        child=ch1[k][i-1]-'A';
        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,e,s,tempv,now_fail;
    e=s=0;
    listb[s++]=Star;
    while(e!=s)
    {
        tempv=listb[e++];
        for(i=0;i<26;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(now_fail==-1)
                    Tree[Tree[tempv].next[i]].fail=0;
                listb[s++]=Tree[tempv].next[i];
            }
        }
    }
}

int Ac_auto(int Tlen)   //BFS匹配
{
    int i,p=0,sum=0,child,temp;
    for(i=1;i<=Tlen;i++)
    {
        if(ch[i-1]<'A'||ch[i-1]>'Z')  //可能出现其他字符，跳过不匹配
        {
            p=0;
            continue;
        }
        child=ch[i-1]-'A';
        while(p!=0&&Tree[p].next[child]==-1)
        {
            p=Tree[p].fail;
        }
        p=(Tree[p].next[child]==-1)?0:Tree[p].next[child];
        temp=p;
        while(temp!=0&&Tree[temp].w!=-1)  //记录出现的次数
        {
            visit[Tree[temp].w]++;
            sum++;                        //不需要擦除
            temp=Tree[temp].fail;
        }
    }
    return sum;
}

int main()
{
    int n,i,k;
    while(scanf("%d",&n)!=EOF)
    {
        Index=1;
        memset(Tree,-1,sizeof(Tree));
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)
        {
            scanf("%s",ch1[i]);
            Insert(0,strlen(ch1[i]),i);  //建立字典树
        }
        Build_fail(0);          //建立失败指针
        getchar();
        gets(ch);               //主串可能有空格
        k=Ac_auto(strlen(ch));  //匹配
        for(i=1;i<=n;i++)
        {
            if(visit[i])
            {
                printf("%s: %d\n",ch1[i],visit[i]);
            }
        }
    }
    return 0;
}