zoj3228 Searching the String AC自动机查询目标串中模式串出现次数(分可覆盖，不可覆盖两种情况)

/**

题目：zoj3228 Searching the String

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3441

题意：给定一个长度为N(N <= 105)的目标串，然后再给定M(M <= 105)个长度不大于6的字符串，

问这些字符串在目标串的出现次数(分可重叠和不可重叠两种)。

题解：可以覆盖情况下，直接建立自动机求次数。注意可能出现类型相同以及字符串相同。所以用map标记；

不可以覆盖情况下，直接建立自动机，查询的时候维护当前查到的字符串上一次找到的位置lastpos.

如果lastpos+该子串长度<=pos那么可以ans++，以及更新lastpos=pos；

find(),find2()两个函数分别处理可覆盖，不可覆盖情况。先统一处理可覆盖，然后清空自动机重新构建不可覆盖情况下的自动机。

AC自动机好文章：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

*/

//#include<bits/stdc++.h>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<map>

#include<algorithm>

#include<queue>

using namespace std;

#define P pair<int,int>

#define ms(x,y) memset(x,y,sizeof x)

#define LL long long

const int maxn = ;

const int mod = 1e9+;

const int maxnode = *+;

const int sigma_size = ;

map<string,int> mp1, mp2;

struct node

{

    char s[];

    int type;

    int len;

    int ans;

    int lastpos;

}t[];

struct AhoCorasickAutomata

{

    int ch[maxnode][sigma_size];

    int val[maxnode];

    int sz;

    int f[maxnode];

    int last[maxnode];

    void clear(){sz = ; memset(ch[],,sizeof ch[]); }

    int idx(char c){return c-'a'; }

    void insert(char *s,int x)

    {

        int u = , n = strlen(s);

        for(int i = ; i < n; i++){

            int c = idx(s[i]);

            if(!ch[u][c]){

                memset(ch[sz], , sizeof ch[sz]);

                val[sz] = ;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = x;

    }

    void find(char* T){

        int j = ;

        for(int i = ; T[i]!='\0'; i++){

            int c = idx(T[i]);

            j = ch[j][c];

            if(val[j]) print(j);

            else if(last[j]) print(last[j]);

        }

    }

    void print(int j)

    {

        if(j){

            //cnt[val[j]]++;

            t[val[j]].ans++;

            print(last[j]);

        }

    }

    void find2(char* T){///不可覆盖情况下；

        int j = ;

        for(int i = ; T[i]!='\0'; i++){

            int c = idx(T[i]);

            j = ch[j][c];

            if(val[j]) print2(j,i);

            else if(last[j]) print2(last[j],i);

        }

    }

    void print2(int j,int pos)

    {

        if(j){

            //cnt[val[j]]++;

            if(t[val[j]].lastpos+t[val[j]].len<=pos){

                t[val[j]].ans++;

                t[val[j]].lastpos = pos;

            }

            print2(last[j],pos);

        }

    }

    void getFail(){

        queue<int> q;

        f[] = ;

        for(int c = ; c < sigma_size; c++){

            int u = ch[][c];

            if(u){f[u] = ; q.push(u); last[u] = ;}

        }

        while(!q.empty()){

            int r = q.front(); q.pop();

            for(int c = ; c < sigma_size; c++){

                int u = ch[r][c];

                if(!u){

                    ch[r][c] = ch[f[r]][c]; continue;

                }//if(!u) continue;

                q.push(u);

                int v = f[r];

                while(v&&!ch[v][c]) v = f[v];

                f[u] = ch[v][c];

                last[u] = val[f[u]] ? f[u] : last[f[u]];

            }

        }

    }

} ac;

char s[];

int main()

{

    int cas = ;

    while(scanf("%s",s)==)

    {

        int n;

        scanf("%d",&n);

        ac.clear();

        mp1.clear();

        mp2.clear();

        for(int i = ; i <= n; i++){

            scanf("%d%s",&t[i].type,t[i].s);

            t[i].ans = ;

            if(t[i].type==){

                mp1[string(t[i].s)] = i;

                ac.insert(t[i].s,i);

            }

        }

        ac.getFail();

        ac.find(s);

        ac.clear();

        mp2.clear();

        for(int i = ; i <= n; i++){

            if(t[i].type){

                t[i].len = strlen(t[i].s);

                t[i].lastpos = -;

                mp2[string(t[i].s)] = i;

                ac.insert(t[i].s,i);

            }

        }

        ac.getFail();

        ac.find2(s);

        printf("Case %d\n",cas++);

        for(int i = ; i <= n; i++){

            if(t[i].type){

                printf("%d\n",t[mp2[t[i].s]].ans);

            }else

            {

                printf("%d\n",t[mp1[t[i].s]].ans);

            }

        }

        printf("\n");

    }

    return ;

}

/*

*/