构建后缀数组然后从大到小遍历后缀选取最优子串即可。注意单独判断一个点如果候选的子串的lcp与已选的相同注意要选取总长度更长的那个子串。这个题是一个不错的SA练习题。AC代码如下分享一个不错的SA板子#includebits/stdc.h using namespace std; struct SA{ int n; string s; vectorintsa,rk,ht,lg; vectorvectorintst; void build(const string _s){ s_s;ns.size(); sa.assign(n,0);rk.assign(n,0);ht.assign(n,0); vectorintx(n),y(n),c(max(256,n)5,0); int m256; for(int i0;in;i)x[i](unsigned char)s[i]; for(int i0;in;i)c[x[i]]; for(int i1;im;i)c[i]c[i-1]; for(int in-1;i0;i--)sa[--c[x[i]]]i; for(int k1,p;kn;k1,mp){ p0; for(int in-k;in;i)y[p]i; for(int i0;in;i)if(sa[i]k)y[p]sa[i]-k; fill(c.begin(),c.begin()m,0); for(int i0;in;i)c[x[y[i]]]; for(int i1;im;i)c[i]c[i-1]; for(int in-1;i0;i--)sa[--c[x[y[i]]]]y[i]; swap(x,y); p1;x[sa[0]]0; for(int i1;in;i){ int asa[i-1],bsa[i]; int a1y[a],b1y[b]; int a2akn?y[ak]:-1; int b2bkn?y[bk]:-1; if(a1b1a2b2)x[b]p-1; else x[b]p; } if(pn)break; } for(int i0;in;i)rk[sa[i]]i; for(int i0,k0;in;i){ if(rk[i]0){k0;continue;} int jsa[rk[i]-1]; while(iknjkns[ik]s[jk])k; ht[rk[i]]k; if(k)k--; } lg.assign(n1,0); for(int i2;in;i)lg[i]lg[i1]1; int Klg[n]1; st.assign(K,vectorint(n,0)); st[0]ht; for(int j1;jK;j){ int len1j,halflen1; for(int i0;ilenn;i){ st[j][i]min(st[j-1][i],st[j-1][ihalf]); } } } int lcp(int a,int b){ if(ab)return n-a; int lrk[a],rrk[b]; if(lr)swap(l,r); l; int lenr-l1,klg[len]; return min(st[k][l],st[k][r-(1k)1]); } int cmp(int a,int b,int c,int d){ int xb-a1,yd-c1; int zlcp(a,c); zmin(z,min(x,y)); if(zmin(x,y)){ if(xy)return 0; return xy?-1:1; } return s[az]s[cz]?-1:1; } }; int T,n,l,k,i,j,res,L,R,ll,rr; string s; SA a; signed main(){ ios::sync_with_stdio(false);cin.tie(0); cinT; while(T--){ cinnlk; cins; if((long long)n-(long long)l*k0){coutNO\n;continue;} resn-l*k; coutYES\n; if(k1){couts\n;continue;} a.build(s);L-1; for(ia.n-1;i0;i--){ ja.sa[i]; if(j0){ if(L0){ Lj;Rjresl; } else{ llj;rrjresl; int lena.lcp(ll,L); if(lenR-L1)lenR-L; if(R-Llenrr-lllen){ Lll;Rrr; } } } else if(jl)continue; else{ if(j%lresjla.n){ if(L0){ Lj; Rmin(a.n,j(res-j%l)l); } else{ llj; rrmin(a.n,j(res-j%l)l); int lena.lcp(ll,L); if(lenR-L1)lenR-L; if(R-Llenrr-lllen){ Lll;Rrr; } } } } } for(iL;iR;i)couts[i];cout\n; } return 0; }