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 Si,Si+1... Sj 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.

solution

还是老套路：利用父节点为最大子集，直接累加儿子出现次数到父亲上面，每一次新加入节点就直接从当前节点跳father，并更新father，如果出现了K次就统计答案，统计方式和上次一样，当前节点所能接受的并且和父亲节点不重合的有 \(len[p]-len[fa[p]]\) 个，注意为了避免重复统计，如果当前节点到了 \(K\)，那么父节点就一定都已经达到了 \(K\)，所以不需要继续跳了

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=400005;

int ch[N][27],fa[N],n,m,K,len[N],cnt=1,cur=1,p,size[N];

char s[5],S[N];long long ans=0;

void build(int c,int id){

   p=cur;cur=++cnt;len[cur]=id;

   for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;

   if(!p)fa[cur]=1;

   else{

      int q=ch[p][c];

      if(len[p]+1==len[q])fa[cur]=q;

      else{

         int nt=++cnt;len[nt]=len[p]+1;

         memcpy(ch[nt],ch[q],sizeof(ch[q]));

         fa[nt]=fa[q];fa[q]=fa[cur]=nt;

         for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;

         size[nt]=size[q];

      }

   }

}

void upd(){

   p=cur;

   while(p>1){

      if(size[p]>=K)return ;

      size[p]++;

      if(size[p]>=K){ans+=len[p]-len[fa[p]];return ;}

      p=fa[p];

   }

}

void Clear(){

   for(RG int i=0;i<N;i++){

      fa[i]=size[i]=len[i]=0;

      for(RG int j=0;j<=26;j++)ch[i][j]=0;

   }

   cur=1;cnt=1;ans=0;

}

void work()

{

   scanf("%s",S+1);

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

      build(S[i]-'a',i);

      upd();

   }

   int flag;

   for(int i=1;i<=m;i++){

      scanf("%d",&flag);

      if(flag==2)printf("%lld\n",ans);

      else{

         scanf("%s",s);

         build(s[0]-'a',++n);upd();

      }

   }

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&K))work(),Clear();

	return 0;

}