zoj 3228 Searching the String(AC自动机基本应用)

题意：给你一个文本串，再给你若干个单词（模板），分为两种，一种是可重复的，另一种是不可能重复的，问你每个单词（模板）在文本中可以找到多少个。

思路：AC自动机基本应用。建立AC自动机，val[u]=1表示该节点为单词尾字母节点，即包含了该单词。至于两种情况，例如文本串为ababa，对于单词aba，若不可重复，则只能找到1个，如果可重复，则可以找到2个。重复的状况就不需要再处理，但是不重复的状态需要再加两个数组，pre数组表示此单词在文本串中上一次出现的位置，len数组记录该单词的长度，对于不能重复的单词，在文本中每找到一个该单词，就判断pre[i]+len[i]是否<=pos(pos为本次找到该单词的位置)。用sum[mx][2]，分别表示该单词重复或者不重复情况下在文本中能找到多少个。

ps：模板各种写错。。。还需要多加练习。。。很多细节还需要自己体会。。。

AC代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int mx=610000;
const int ssize=26;
struct ACzdj{
    int ch[mx][ssize];
    int val[mx];
    int f[mx],last[mx];
    int pre[mx],len[mx];
    int sum[mx][2];
    int sz;
    void init()
    {
     memset(ch[0],0,sizeof(ch[0]));
     val[0]=0;
     f[0]=last[0]=0;
     sz=1;
    }
    void add(char *s)
    {
        int u=0,n=strlen(s);
        for(int i=0;i<n;i++)
        {
         int id=s[i]-'a';
         if(ch[u][id]==0)
         {
          ch[u][id]=sz;
          memset(ch[sz],0,sizeof(ch[sz]));
          val[sz++]=0;
         }
        u=ch[u][id];
        }
        val[u]=1;
        len[u]=n;
        pre[u]=0;
        sum[u][0]=sum[u][1]=0;
    }
    void getFail()
    {
        queue<int>q;
        for(int i=0;i<ssize;i++)
        {
         int u=ch[0][i];
         if(!u) continue;
         q.push(u);
         last[u]=f[u]=0;
        }
        while(!q.empty())
        {
         int r=q.front();q.pop();
         for(int i=0;i<ssize;i++)
         {
         int u=ch[r][i];
         if(!u) continue;
         q.push(u);
         int v=f[r];
         while(v&&ch[v][i]==0) v=f[v];
         f[u]=ch[v][i];
         last[u]=val[f[u]]?f[u]:last[f[u]];
         }
        }
    }
    void print(int i,int pos)
    {
        if(val[i])
        {
            sum[i][0]++;
            if(pre[i]+len[i]<=pos) {sum[i][1]++;pre[i]=pos;}
            print(last[i],pos);
        }
    }
    int find(char *s,int cnt)//该find找单词出现的次数，即最终结果
    {
        int u=0,n=strlen(s);
        for(int i=0;i<n;i++)
        {
         int id=s[i]-'a';
            u=ch[u][id];
        }
        return sum[u][cnt];
    }
    void find2(char *s)//该find负责计数，找所有单词重复的不重复的出现了多少次。
    {
        int n=strlen(s),j=0;
        for(int i=0;i<n;i++)
        {
         int id=s[i]-'a';
         while(j&&ch[j][id]==0) j=f[j];
         j=ch[j][id];
         if(val[j]) print(j,i+1);
         else if(last[j]) print(last[j],i+1);
        }
    }
}ac;
char txt[110000];
char ss[100010][8];
int b[100010];
int main()
{
    int n;
    int cas=1;
    while(scanf("%s",txt)!=EOF)
    {
        ac.init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
         scanf("%d%s",&b[i],ss[i]);
         ac.add(ss[i]);
        }
        ac.getFail();
        ac.find2(txt);
        printf("Case %d\n",cas++);
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",ac.find(ss[i],b[i]));
        }
        puts("");
    }
}