Educational Codeforces Round 189 (Rated for Div. 2) F. String Cutting
构建后缀数组，然后从大到小遍历后缀，选取最优子串即可。
注意单独判断一个点：如果候选的子串的lcp与已选的相同，注意要选取总长度更长的那个子串。
这个题是一个不错的SA练习题。
AC代码如下：（分享一个不错的SA板子）
#include<bits/stdc++.h> using namespace std; struct SA{ int n; string s; vector<int>sa,rk,ht,lg; vector<vector<int>>st; void build(const string &_s){ s=_s;n=s.size(); sa.assign(n,0);rk.assign(n,0);ht.assign(n,0); vector<int>x(n),y(n),c(max(256,n)+5,0); int m=256; for(int i=0;i<n;i++)x[i]=(unsigned char)s[i]; for(int i=0;i<n;i++)c[x[i]]++; for(int i=1;i<m;i++)c[i]+=c[i-1]; for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i; for(int k=1,p;k<n;k<<=1,m=p){ p=0; for(int i=n-k;i<n;i++)y[p++]=i; for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k; fill(c.begin(),c.begin()+m,0); for(int i=0;i<n;i++)c[x[y[i]]]++; for(int i=1;i<m;i++)c[i]+=c[i-1]; for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(int i=1;i<n;i++){ int a=sa[i-1],b=sa[i]; int a1=y[a],b1=y[b]; int a2=a+k<n?y[a+k]:-1; int b2=b+k<n?y[b+k]:-1; if(a1==b1&&a2==b2)x[b]=p-1; else x[b]=p++; } if(p>=n)break; } for(int i=0;i<n;i++)rk[sa[i]]=i; for(int i=0,k=0;i<n;i++){ if(rk[i]==0){k=0;continue;} int j=sa[rk[i]-1]; while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++; ht[rk[i]]=k; if(k)k--; } lg.assign(n+1,0); for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; int K=lg[n]+1; st.assign(K,vector<int>(n,0)); st[0]=ht; for(int j=1;j<K;j++){ int len=1<<j,half=len>>1; for(int i=0;i+len<=n;i++){ st[j][i]=min(st[j-1][i],st[j-1][i+half]); } } } int lcp(int a,int b){ if(a==b)return n-a; int l=rk[a],r=rk[b]; if(l>r)swap(l,r); l++; int len=r-l+1,k=lg[len]; return min(st[k][l],st[k][r-(1<<k)+1]); } int cmp(int a,int b,int c,int d){ int x=b-a+1,y=d-c+1; int z=lcp(a,c); z=min(z,min(x,y)); if(z==min(x,y)){ if(x==y)return 0; return x<y?-1:1; } return s[a+z]<s[c+z]?-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); cin>>T; while(T--){ cin>>n>>l>>k; cin>>s; if((long long)n-(long long)l*k<0){cout<<"NO"<<'\n';continue;} res=n-l*k; cout<<"YES"<<'\n'; if(k==1){cout<<s<<'\n';continue;} a.build(s);L=-1; for(i=a.n-1;i>=0;i--){ j=a.sa[i]; if(j==0){ if(L<0){ L=j;R=j+res+l; } else{ ll=j;rr=j+res+l; int len=a.lcp(ll,L); if(len>R-L+1)len=R-L; if(R-L==len&&rr-ll>len){ L=ll;R=rr; } } } else if(j<l)continue; else{ if(j%l<=res&&j+l<=a.n){ if(L<0){ L=j; R=min(a.n,j+(res-j%l)+l); } else{ ll=j; rr=min(a.n,j+(res-j%l)+l); int len=a.lcp(ll,L); if(len>R-L+1)len=R-L; if(R-L==len&&rr-ll>len){ L=ll;R=rr; } } } } } for(i=L;i<R;i++)cout<<s[i];cout<<'\n'; } return 0; }