题意：
在长度为 N 的主串中选取一个长度为 K 的子串可以把原主串全覆盖。覆盖的条件是 选取的子串 s 把原串中所有长度为 K 并且字典序小于 s 的子串的字符标记之后（每个字符可被标记多次），
如果原串的全部字符都被标记，则当前选取的子串 s 可以覆盖这个主串。
求字典序最小的 s 。原串是一个环！！！即最小化最大值。
思路：后缀数组，直接开2倍长度跑SA就好了，因为我们要找一个满足能标记完n个字符的排名最小的长度为k的子串，所以我们可以二分排名check一下长度是否大于等于n就好了。
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #include<vector> #include<map> #include<set> #include<queue> #include<stack> //#define _for(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; double eps=0.05; ll mod=1e9+7; const int INF=0x3f3f3f3f,inf =0x3f3f3f3f; const int MAXN=2e3+10; const int maxn = 1e7+10; //ll inf=100000000000000; //template<typename T>inline void read(T &x) //{ // x=0; // static int p;p=1; // static char c;c=getchar(); // while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} // while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} // x*=p; //} typedef unsigned long long ull; const int N=2e6+7; const double PI=acos(-1.0); char ss[N]; int s[N]; int sa[N],t[N],t2[N],c[N];//y[N]; int rk[N],H[N]; void build_sa(int n,int m){ int i,*x=t,*y=t2; for( i=0;i<m;i++)c[i]=0; for( i=0;i<n;i++)c[x[i]=s[i]]++; for( i=1;i<m;i++)c[i]+=c[i-1]; for( i=n-1;i>=0;i--)sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){ int p=0; for(i=n-k;i<n;i++)y[p++]=i; for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(i=0;i<m;i++)c[i]=0; for(i=0;i<n;i++)c[x[y[i]]]++; for(i=0;i<m;i++)c[i]+=c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; if(p>=n)break; m=p; } } void getH(int n){ int i,j,k=0; for(i=0;i<n;i++)rk[sa[i]]=i; for(i=0;i<n;i++){ if(k)k--; int j=sa[rk[i]-1]; while(s[i+k]==s[j+k])k++; H[rk[i]]=k; } } //void SA(int n,int m){ // for(int i=0;i<m;i++) c[i]=0; // for(int i=0;i<n;i++) c[rk[i]=s[i]]++; // for(int i=1;i<m;i++) c[i]+=c[i-1]; // for(int i=n-1;i>=0;i--) sa[--c[rk[i]]]=i; // for(int k=1;k<=n;k<<=1){ // int num=0; // for(int i=n-k;i<n;i++) y[num++]=i; // for(int i=0;i<n;i++) if(sa[i]>=k) y[num++]=sa[i]-k; // for(int i=0;i<m;i++) c[i]=0; // for(int i=0;i<n;i++) c[rk[i]]++; // for(int i=1;i<m;i++) c[i]+=c[i-1]; // for(int i=n-1;i>=0;i--) // sa[--c[rk[y[i]]]]=y[i]; // swap(rk,y); // rk[sa[0]]=0; num=1; // for(int i=1;i<n;i++) // rk[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? num-1:num++); // if(num>=n) break; // m=num; // } //} //void HH (int n){ // for(int i=1;i<=n;i++) sa[rk[i]]=i; // for(int i=0,k=0;i<n;i++){ // if(k) k--; else k=0; // int j=sa[rk[i]-1]; // while(s[i+k]==s[j+k]) k++; // H[rk[i]]=k; // } //} bool check(int mid,int n,int k){ int st=0,en=-1; for(int i=0;i<n;i++){ if(rk[i]>mid) continue; if(en<i) st=i; en=i+k; if(en-st>=n) return true; } return false; } int main() { int n,k; scanf("%d%d",&n,&k); scanf("%s",ss); for(int i=0;i<n;i++)ss[n+i]=ss[i]; for(int i=0;i<2*n;i++)s[i]=ss[i]-'a'+1; n<<=1; s[n]=0; // for(int i=0;i<n;i++)printf("%d",s[i]); // cout<<endl; build_sa(n+1,30); //SA(n+1,30); getH(n+1); //HH(n); // for(int i=0;i<n;i++){ // printf("%d ",sa[i]); // } // cout<<endl; // for(int i=0;i<n;i++){ // printf("%d ",rk[i]); // } // cout<<endl; int l=0,r=n,ans; while(l<=r){ int mid = (l+r)>>1; if(check(mid,n,k)) r=mid-1,ans=mid; else l=mid+1; } for(int i=0;i<n;i++){ if(rk[i]==ans){ for(int j=i;j<i+k;j++) printf("%c",ss[j]); return 0; } } // int l=0,r=n,ans; // while(l<=r){ // int mid=(l+r)>>1; // if(check(mid,n,k))r=mid-1,ans=mid; // else l=mid+1; // } // cout<<ans<<endl; // cout<<ss<<endl; // for(int i=0;i<n;i++){ // if(rk[i]==ans){ // cout<<i<<" "<<i+k<<endl; // for(int j=i;j<i+k;j++){ // printf("%c",ss[j]); // } // return 0; // } //} return 0; }