【AC自动机】zoj3228 Searching the String

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue<int>q;
bool word[601000];
int child[601000][26],fail[601000],size,pos[101000];
int cnta[601000],cntb[601000],posn[601000],lens[601000];
void Insert(char S[],int id)
{
    int len=strlen(S);
    int now=0;
    for(int i=0;i<len;++i)
      {
        if(!child[now][S[i]-‘a‘])
          child[now][S[i]-‘a‘]=size++;
        now=child[now][S[i]-‘a‘];
      }
    word[now]=1;
    lens[now]=len;
    pos[id]=now;
}
void build()
{
    fail[0]=-1;
    q.push(0);
    while(!q.empty())
      {
        int U=q.front(); q.pop();
        for(int i=0;i<26;++i)
          if(child[U][i])
            {
              int V=fail[U];
              while(V!=-1)
                {
                  if(child[V][i])
                    {
                      fail[child[U][i]]=child[V][i];
                      break;
                    }
                  V=fail[V];
                }
              if(V==-1)
                fail[child[U][i]]=0;
              q.push(child[U][i]);
            }
      }
}
void match(char S[])
{
    int len=strlen(S);
    int res=0,now=0;
    for(int i=0;i<len;++i)
      {
        if(child[now][S[i]-‘a‘])
          now=child[now][S[i]-‘a‘];
        else
          {
            int U=fail[now];
            while(U!=-1 && child[U][S[i]-‘a‘]==0)
              U=fail[U];
            if(U==-1)
              now=0;
            else
              now=child[U][S[i]-‘a‘];
          }
        int U=now;
        while(U)
          {
          	if(word[U])
          	  {
          	  	++cnta[U];
          	  	if(posn[U]<=i-lens[U])
          	  	  {
          	  	  	++cntb[U];
          	  	  	posn[U]=i;
          	  	  }
          	  }
          	U=fail[U];
          }
      }
}
void Init()
{
    memset(child,0,sizeof(child));
    memset(fail,0,sizeof(fail));
    memset(word,0,sizeof(word));
    memset(pos,0,sizeof(pos));
    memset(cnta,0,sizeof(cnta));
    memset(cntb,0,sizeof(cntb));
    memset(posn,-1,sizeof(posn));
    memset(lens,0,sizeof(lens));
    size=1;
}
char s[101000];
bool op[101000];
int n;
int main()
{
	char ss[9];
	int T=0;
	//freopen("zoj3228.in","r",stdin);
	while(scanf("%s%d",s,&n)!=EOF)
	  {
	  	printf("Case %d\n",++T);
	  	Init();
	  	for(int i=1;i<=n;++i)
	  	  {
	  	  	scanf("%d%s",&op[i],ss);
	  	  	Insert(ss,i);
	  	  }
	  	build();
	  	match(s);
	  	for(int i=1;i<=n;++i)
	  	  printf("%d\n",op[i] ? cntb[pos[i]] : cnta[pos[i]]);
	  	puts("");
	  }
	return 0;
}