首先求出后缀数组，得到本质不同的子串的个数。

然后二分答案，每次先通过后缀数组求出第$mid$小的子串，然后贪心进行检验。

检验的时候，从后往前贪心，每次加入一个后缀，如果不能加了，那就划为一段。

时间复杂度$O(n\log n)$。

 

#include
     
      #include
      
       #include
       
        #define N 100010using namespace std;typedef long long ll;char s[N];int K,n,i,j,rk[N],sa[N],height[N],tmp[N],cnt[N],Log[N],f[16][N],g[N];ll L=1,R,mid;int len,nowl,nowr,ansl,ansr;void suffixarray(int n,int m){  int i,j,k;n++;  for(i=0;i
        
         =n-1)break;  }  for(j=rk[height[i=k=0]=0];i
         
          y)swap(x,y);  int k=Log[y-x];  return min(f[k][x+1],f[k][y-(1<
          
           =k){ nowl=sa[i],nowr=nowl+height[i]+k-s-1; len=nowr-nowl+1; return; }}inline bool ask(int l,int r){ int t=min(lcp(l,nowl),min(r-l+1,len)); if(t==r-l+1&&t<=len)return 1; if(t==len)return 0; return s[l+t]<=s[nowl+t];}bool check(){ int i,j,k=0; for(i=n-1;~i;i=j,k++){ for(j=i;~j;j--)if(!ask(j,i))break; if(j==i)return 0; } return k<=K;}int main(){ scanf("%d%s",&K,s); n=strlen(s); suffixarray(n,128); for(i=2;i<=n;i++)Log[i]=Log[i>>1]+1; for(i=1;i<=n;i++)f[0][i]=height[i]; for(j=1;j<17;j++)for(i=1;i+(1<
           
            <=n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<
            
             >1); if(check())ansl=nowl,ansr=nowr,R=mid-1;else L=mid+1; } for(i=ansl;i<=ansr;i++)putchar(s[i]); return 0;}