zoj 3228 Searching the String

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3228

题目大意： 给出一串主串，然后下面有n串模式串，模式串前面有一个值，
0：在主串中有多少串该模式串，假如aaa 找aa，那么就有2串
1：在主串中有多少串该模式串，并且不能有重叠部分，假如aaa找aa，那么只有1串

题目思路：ac自动机。不知道存不存在相同字符串且相同类型重复询问的情况，为了保险，我还是用了一个hash,将相同的询问hash成一个值，然后将在一个位置里面存两个值，类型0和类型1的id,这样就可以分开计算了，对于类型1，其实就是贪心，只要记录前一次匹配的位置就可以了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define M 110000
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int q[6*M],cnt;
int hash[M],pre[M],num[M];
char s[M];
char str[10];
int n,m;
struct node
{
    int fail,id[2];
    int len;
    int next[26];
    void init()
    {
        fail=0;
        id[0]=id[1]=-1;
        memset(next,0,sizeof(next));
    }
}tri[6*M];
void insert(char *s,int id,int tp)
{
    int i,p,x;
    p=0;
    for(i=0;s[i];i++)
    {
        x=s[i]-'a';
        if(!tri[p].next[x])
        {
            tri[++cnt].init();
            tri[p].next[x]=cnt;
        }
        p=tri[p].next[x];
    }
    if(tri[p].id[tp]==-1)
    {
        tri[p].id[tp]=id;
        hash[id]=id;
        tri[p].len=strlen(s);
    }
    else
    {
        hash[id]=tri[p].id[tp];
    }
}
void bfs()
{
    int i,p,suf,head,tail;
    p=head=tail=0;
    for(i=0;i<26;i++)
    {
        if(tri[0].next[i])
        {
            q[tail++]=tri[0].next[i];
            tri[q[tail-1]].fail=0;
        }
    }
    while(head<tail)
    {
        p=q[head++];suf=tri[p].fail;
        for(i=0;i<26;i++)
        {
            if(tri[p].next[i])
            {
                q[tail++]=tri[p].next[i];
                tri[q[tail-1]].fail=tri[suf].next[i];
            }
            else
                tri[p].next[i]=tri[suf].next[i];
        }
    }
}
void solve()
{
    int i,x,p,tmp;
    p=0;
    for(i=0;s[i];i++)
    {
        x=s[i]-'a';
        p=tri[p].next[x];
        tmp=p;
        while(tmp)
        {
            if(tri[tmp].id[0]+1)
            {
                num[tri[tmp].id[0]]++;
            }
            if(tri[tmp].id[1]+1)
            {
                if(pre[tri[tmp].id[1]]!=-1)
                {
                    if(tri[tmp].len<=i-pre[tri[tmp].id[1]])
                    {
                        pre[tri[tmp].id[1]]=i;
                        num[tri[tmp].id[1]]++;
                    }
                }
                else
                {
                    pre[tri[tmp].id[1]]=i;
                    num[tri[tmp].id[1]]++;
                }
            }
            tmp=tri[tmp].fail;
        }
    }
}
int main()
{
    int i,tp,count=1;
    while(scanf("%s",s)!=EOF)
    {
        scanf("%d",&m);
        cnt=0;
        tri[0].init();
        memset(num,0,sizeof(num));
        memset(pre,-1,sizeof(pre));
        for(i=1;i<=m;i++)
        {
            scanf("%d%s",&tp,str);
            insert(str,i,tp);
        }
        bfs();
        solve();
        printf("Case %d\n",count++);
        for(i=1;i<=m;i++)
        {
            printf("%d\n",num[hash[i]]);
        }
        puts("");
    }
}