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

分析

TJOI白给题

建出sam,对于每个点如果它的子树siz和等于k

那么对于这个满足的点它有贡献的长度一定是一个连续区间

直接差分即可

代码

#include<bits/stdc++.h>

using namespace std;

int n,k,mx,ans,d[];

char s[];

struct SAM {

    int mp[][],fa[],ed,ccnt,len[],siz[];

    int head[],nxt[],to[],cnt;

    inline void init(){

      mx=;

      cnt=ans=;

      ccnt=ed=;

      memset(d,,sizeof(d));

      memset(mp,,sizeof(mp));

      memset(fa,,sizeof(fa));

      memset(to,,sizeof(to));

      memset(len,,sizeof(len));

      memset(siz,,sizeof(siz));

      memset(nxt,,sizeof(nxt));

      memset(head,,sizeof(head));

    }

    inline void add(int x,int y){

      nxt[++cnt]=head[x];

      head[x]=cnt;

      to[cnt]=y;

    }

    inline void ins(int x,int n1){

        int p=ed;

        ed=++ccnt;

        siz[ccnt]=;

        len[ccnt]=n1;

        while(p&&!mp[p][x]){

          mp[p][x]=ed;

          p=fa[p];

        }

        if(!p){

          fa[ed]=;

          return;

        }

        int q=mp[p][x];

        if(len[q]==len[p]+){

          fa[ed]=q;

          return;

        }

        len[++ccnt]=len[p]+;

        for(int i=;i<=;i++)mp[ccnt][i]=mp[q][i];

        fa[ccnt]=fa[q];

        fa[q]=ccnt;

        fa[ed]=ccnt;

        for(int i=p;mp[i][x]==q;i=fa[i])mp[i][x]=ccnt;

    }

    inline void build(){

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

    }

    inline void dfs(int x){

      for(int i=head[x];i;i=nxt[i])

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

      if(siz[x]==k&&len[fa[x]]+<=len[x])d[len[fa[x]]+]++,d[len[x]+]--;

    }

};

SAM sam;

int main(){

    int i,j,t;

    scanf("%d",&t);

    while(t--){

      sam.init();

      scanf("%s",s+);

      n=strlen(s+);

      scanf("%d",&k);

      for(i=;i<=n;i++)sam.ins(s[i]-'a'+,i);

      sam.build();

      sam.dfs();

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

          d[i]+=d[i-];

          if(d[i]&&d[i]>=mx){

            mx=d[i];

            ans=i;

        }

      }

      printf("%d\n",ans?ans:-);

    }

    return ;

}