hdu4641-K-string(后缀自动机)

Problem Description

Given a string S. K-string is the sub-string of S and it appear in the S at least K times.It means there are at least K different pairs (i,j) so that S_i,S_i+1... S_j equal to this K-string. Given m operator or query:1.add a letter to the end of S; 2.query how many different K-string currently.For each query ,count the number of different K-string currently.

Input

The input consists of multiple test cases. Each test case begins with a line containing three integers n, m and K(1<=n,K<=50000,1<=m<=200000), denoting the length of string S, the number of operator or question and the least number of occurrences of K-string in the S. The second line consists string S,which only contains lowercase letters. The next m lines describe the operator or query.The description of the operator looks as two space-separated integers t c (t = 1; c is lowercase letter).The description of the query looks as one integer t (t = 2).

Output

For each query print an integer — the number of different K-string currently.

Sample Input

3 5 2

abc

1 a

Sample Output

题意: 开始时给出一个字符串,给出两种操作,一种是在字符串后面添加一个字符,
另一个是查询出现过K次的字串个数。
解析: 建立后缀自动机,添加一个字符插入即可,对于查询,前面计算过的没必要再算,
直接从当前开始往前面找,已经达到K次的就不管,说明前面已经计算过,现在达到
K次的加进答案。

代码

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int maxn=;

int N,M,K;

struct SAM

{

    int ch[maxn][];

    int pre[maxn],step[maxn];

    int last,id,ans;

    int num[maxn];

    void init()

    {

        ans=last=id=;

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

        pre[]=-; step[]=;

    }

    void Insert(int c)

    {

        int p=last,np=++id;

        step[np]=step[p]+;

        memset(ch[np],-,sizeof(ch[np])); num[np]=;

        while(p!=-&&ch[p][c]==-)  ch[p][c]=np,p=pre[p];

        if(p==-) pre[np]=;

        else

        {

            int q=ch[p][c];

            if(step[q]!=step[p]+)

            {

                int nq=++id;

                memcpy(ch[nq],ch[q],sizeof(ch[q])); num[nq]=num[q];

                step[nq]=step[p]+;

                pre[nq]=pre[q];

                pre[np]=pre[q]=nq;

                while(p!=-&&ch[p][c]==q) ch[p][c]=nq,p=pre[p];

            }

            else pre[np]=q;

        }

        last=np;

        while(np!=-&&num[np]<K) //没有达到K次的就加1

        {

            num[np]++;

            if(num[np]>=K) ans+=step[np]-step[pre[np]]; //加上答案

            np=pre[np];

        }

    }

}sam;

char S[];

int main()

{

    while(scanf("%d%d%d",&N,&M,&K)!=EOF)

    {

        scanf("%s",S);

        sam.init();

        for(int i=;i<N;i++) sam.Insert(S[i]-'a');

        int type;

        char c;

        while(M--)

        {

            scanf("%d",&type);

            if(type==){ scanf(" %c",&c); sam.Insert(c-'a'); }

            else printf("%d\n",sam.ans);

        }

    }

    return ;

}

秒客网

hdu4641-K-string(后缀自动机)

相关文章