分析
TJOI白给题
建出sam,对于每个点如果它的子树siz和等于k
那么对于这个满足的点它有贡献的长度一定是一个连续区间
直接差分即可
代码
#include<bits/stdc++.h>
using namespace std;
int n,k,mx,ans,d[100100];
char s[100100];
struct SAM {int mp[200100][30],fa[200100],ed,ccnt,len[200100],siz[200100];int head[200100],nxt[200100],to[200100],cnt;inline void init(){mx=0;cnt=ans=0;ccnt=ed=1;memset(d,0,sizeof(d));memset(mp,0,sizeof(mp));memset(fa,0,sizeof(fa));memset(to,0,sizeof(to));memset(len,0,sizeof(len));memset(siz,0,sizeof(siz));memset(nxt,0,sizeof(nxt));memset(head,0,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]=1;len[ccnt]=n1;while(p&&!mp[p][x]){mp[p][x]=ed;p=fa[p];}if(!p){fa[ed]=1;return;}int q=mp[p][x];if(len[q]==len[p]+1){fa[ed]=q;return;}len[++ccnt]=len[p]+1;for(int i=1;i<=26;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=2;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]]+1<=len[x])d[len[fa[x]]+1]++,d[len[x]+1]--;}
};
SAM sam;
int main(){int i,j,t;scanf("%d",&t);while(t--){sam.init();scanf("%s",s+1);n=strlen(s+1);scanf("%d",&k);for(i=1;i<=n;i++)sam.ins(s[i]-'a'+1,i);sam.build();sam.dfs(1);for(i=1;i<=n;i++){d[i]+=d[i-1];if(d[i]&&d[i]>=mx){mx=d[i];ans=i;}}printf("%d\n",ans?ans:-1);}return 0;
} 
