zoj3223

其实这题不超时完全是因为串长度太小，如果串够长，一次匹配后都要往上跳，复杂度是n^2的。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=,APB=,one=,INF=0x7FFFFFFF,mod=;

int n,cnt,dp[SZ][],pre[SZ],len[SZ];

int nex[SZ][APB],fail[SZ];

struct nd{

    int pos,type;

    nd(int a=,int b=):pos(a),type(b){}

};

nd qry[SZ];

char ch[SZ],str[];

void add(int x)

{

    int cur=;

    for(int i=;str[i];++i)

    {

        int c=str[i]-'a';

        if(!nex[cur][c])nex[cur][c]=++cnt;

        cur=nex[cur][c];

    }

    qry[x].pos=cur;

    len[cur]=strlen(str+);

}

void build()

{

    queue<int> q;

    q.push();

    for(;q.size();)

    {

        int fr=q.front();

        q.pop();

        for(int i=;i<APB;++i)

        {

            int t=nex[fr][i];

            if(t)

            {

                if(!fr)

                {

                    fail[t]=fr;

                }

                else

                {

                    int u=fail[fr];

                    for(;u&&!nex[u][i];u=fail[u]);

                    u=nex[u][i];

                    fail[t]=u;

                }

                q.push(t);

            }

        }

    }

}

void init()

{

    //cin>>n;

    scanf("%d",&n);

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

    {

        int type;

        //cin>>type>>str+1;

        scanf("%d",&type);

        scanf(" %s",str+);

        add(i);

        qry[i].type=type;

    }

    build();

}

int getnex(int x,int c)

{

    for(;x&&!nex[x][c];x=fail[x]);

    x=nex[x][c];

    return x;

}

void update(int x,int pos)

{

    for(;x;x=fail[x])

    {

        ++dp[x][];

        if(pos-pre[x]>=len[x])

        {

            ++dp[x][];

            pre[x]=pos;

        }

    }

}

void work()

{

    int cur=;

    for(int i=;ch[i];++i)

    {

        int c=ch[i]-'a';

        cur=getnex(cur,c);

        update(cur,i);

    }

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

    {

        printf("%d\n",dp[qry[i].pos][qry[i].type]);

        //cout<<<<endl;

    }

}

void release()

{

    for(int i=;i<=cnt;++i)

    {

        memset(nex[i],,sizeof(nex[i]));

        memset(dp[i],,sizeof(dp[i]));

        pre[i]=;

    }

    cnt=0LL;

}

int main()

{

    //std::ios::sync_with_stdio(0);

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //cout<<casenum<<endl;

    //for(int time=1;time<=casenum;++time)

    for(int time=;scanf(" %s",ch+)!=EOF;++time)

    {

        //cout<<""<<<<endl;

        //if(time!=1)

        printf("Case %d\n",time);

        init();

        work();

        release();printf("\n");

    }

    return ;

}