luogu P5341 [TJOI2019]甲苯先生和大中锋的字符串

考虑子串以及出现个数,可以发现SAM可以快速知道每种子串的出现次数,即所在状态的\(endpos\)集合大小,然后一个状态对应的子串长度是一段连续区间,所以可以对每个状态差分一下,就能统计答案了

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=2e5+10;

/*int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}*/ //垃圾luogu数据卡读优

int to[N],nt[N],hd[N],tot;

void add(int x,int y)

{

    ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;

}

char cc[N];

int n,kk,b[N],la,tt,fa[N],ch[N][26],len[N],sz[N];

int newnode(){++tt,fa[tt]=len[tt]=sz[tt]=0;memset(ch[tt],0,sizeof(int)*26);return tt;}

void extd(int x)

{

    int np=newnode(),p=la;

    len[np]=len[p]+1,sz[np]=1,la=np;

    while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];

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

    else

    {

        int q=ch[p][x];

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

        else

        {

            int nq=newnode();

            fa[nq]=fa[q],len[nq]=len[p]+1,memcpy(ch[nq],ch[q],sizeof(ch[q]));

            fa[np]=fa[q]=nq;

            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];

        }

    }

}

void dfs(int x)

{

    for(int i=hd[x];i;i=nt[i])

        dfs(to[i]),sz[x]+=sz[to[i]];

    if(sz[x]==kk) ++b[len[fa[x]]+1],--b[len[x]+1];

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

        n=strlen(cc+1);

        scanf("%d",&kk);

        for(int i=1;i<=n;++i) b[i]=0;

        la=1,tt=0,newnode();

        for(int i=1;i<=n;++i) extd(cc[i]-'a');

        memset(hd,0,sizeof(int)*(tt+3)),tot=0;

        for(int i=2;i<=tt;++i) add(fa[i],i);

        dfs(1);

        int ans=-1,ma=0;

        for(int i=1;i<=n;++i) b[i]+=b[i-1];

        for(int i=n;i;--i)

            if(ma<b[i]) ma=b[i],ans=i;

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

luogu P5341 [TJOI2019]甲苯先生和大中锋的字符串

最新文章

热门文章