学步园

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3065

题目意思：

给你n个子串，问你在一个大的字符串里面每个子串出现了多少次

裸的AC自动机

就是统计那里稍作改动

对于每一个子串的结尾的val[u]=v

这个v就是第几个的意思，便于后面统计

然后加入统计函数

void tongji(int j)
{
    if(j)
    {
        ans[val[j]]++;
        tongji(last[j]);
    }
}

有了这个函数，就可以清楚的统计出来

下面上完整的代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

const int maxnode = 1000*50+10;
const int size=130;
const int maxn = 1000+10;
int ans[maxn];


struct AC
{
    int ch[maxnode][size];
    int f[maxnode];
    int last[maxnode];
    int val[maxnode];
    int sz;

    void init()
    {
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
    }

    void insert(char *s,int v)
    {
        int u=0;
        int n=strlen(s);
        for(int i=0;i<n;i++)
        {
            int c=s[i];
            if(!ch[u][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=v;
    }

    void tongji(int j)
    {
        if(j)
        {
            ans[val[j]]++;
            tongji(last[j]);
        }
    }

    void find(char *T)
    {
        int u=0;
        int n=strlen(T);
        for(int i=0;i<n;i++)
        {
            int c=T[i];
            while(u&&!ch[u][c])
                u=f[u];
            u=ch[u][c];
            if(val[u])
                tongji(u);
            else if(last[u])
                tongji(last[u]);
        }
    }

    void getfail()
    {
        queue<int>q;
        f[0]=0;
        int u;
        for(int i=0;i<size;i++)
        {
            u=ch[0][i];
            if(u){f[u]=0;q.push(u);last[u]=0;}
        }

        while(!q.empty())
        {
            int r=q.front();q.pop();
            for(int i=0;i<size;i++)
            {
                int u=ch[r][i];
                if(!u)continue;
                q.push(u);
                int v=f[r];
                while(v&&!ch[v][i])v=f[v];
                f[u]=ch[v][i];
                last[u]=val[u]?f[u]:last[f[u]];
            }
        }

    }
};

char p[maxn][60];
char text[2000000+20];
AC ac;

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(ans,0,sizeof(ans));
        ac.init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",p[i]);
            ac.insert(p[i],i);
        }
        ac.getfail();
        scanf("%s",text);
        ac.find(text);
        for(int i=1;i<=n;i++)
        {
            if(ans[i])
            {
                printf("%s: %d\n",p[i],ans[i]);
            }
        }
    }
    return 0;
}