题目描述
很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
现在他想找一个最优的分法让“魔力串”字典序最小。
输入
第一行一个整数 k。
接下来一个长度不超过 105 的字符串 S。
输出
输出一行，表示字典序最小的“魔力串”。
样例输入
13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba
样例输出
cbc
题解
后缀数组+二分
先使用后缀数组求出sa、rank和height，然后预处理出ST表，用倍增RMQ求LCP（再次偷改height的定义，height[i][j]表示sa[i]与sa[i-(1<<j)]的LCP）
然后我们二分答案串在S的所有子串中的排名。
这里用到了一个挺好理解的结论：一个串的本质不同的子串的个数为$\sum\limits_{i=1}^nn-sa[i]-height[i]$，就是某个字符开头的串的个数-重复出现过的串的个数。
有个这个结论可以做点什么？首先我们可以确定二分边界。
然后我们还可以根据子串的排名mid来求出对应的子串。
怎么求？我们从前往后枚举i，算出以sa[i]开头的本质不同的子串个数n-sa[i]-height[i]，如果mid大于这个数就将mid减去这个数，否则对应的子串就是sa[i]开头，sa[i]+height[i]-1+mid结尾的字符串。退推一下，应该不是很难想。
那么有了子串以后，我们在原串上从后往前贪心，每次找到一个字符，就比较当前串和二分的子串的字典序大小关系，如果当前的子串字典序较大，则在这个找到的字符后面分割一下。最后比较分割次数与k的关系即可。
需要注意的是二分的子串必须大于等于单个的最大字符，否则无论怎样分割都不可能分割出小于等于该串的字符串。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int sa[N] , r[N] , ws[N] , wa[N] , wb[N] , rank[N] , height[N][20] , n , m = 27 , log[N] , k , L , R;
char str[N];
void getsa()
{
int i , j , p , *x = wa , *y = wb;
for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ;
for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];
for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i;
for(p = j = 1 ; p < n ; j <<= 1 , m = p)
{
for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i;
for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j;
for(i = 0 ; i < m ; i ++ ) ws[i] = 0;
for(i = 0 ; i < n ; i ++ ) ws[x[y[i]]] ++ ;
for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];
for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i];
for(swap(x , y) , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ )
{
if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p - 1;
else x[sa[i]] = p ++ ;
}
}
for(i = 1 ; i < n ; i ++ ) rank[sa[i]] = i;
for(p = i = 0 ; i < n - 1 ; height[rank[i ++ ]][0] = p)
for(p ? p -- : 0 , j = sa[rank[i] - 1] ; r[i + p] == r[j + p] ; p ++ );
}
void query(ll mid)
{
int i;
for(i = 1 ; i <= n ; i ++ )
{
if(n - sa[i] - height[i][0] < mid) mid -= n - sa[i] - height[i][0];
else
{
L = sa[i] , R = sa[i] + height[i][0] + mid - 1;
return;
}
}
L = 0 , R = n - 1;
}
int lcp(int x , int y)
{
if(x == y) return n;
x = rank[x] , y = rank[y];
if(x > y) swap(x , y);
int k = log[y - x];
return min(height[y][k] , height[x + (1 << k)][k]);
}
bool cmp(int l1 , int r1 , int l2 , int r2)
{
int t = lcp(l1 , l2) , len1 = r1 - l1 + 1 , len2 = r2 - l2 + 1;
if(len1 <= len2 && len1 <= t) return 1;
if(len1 > len2 && len2 <= t) return 0;
if(len1 <= t && len2 <= t) return len1 <= len2;
return r[l1 + t] <= r[l2 + t];
}
bool judge()
{
int i , cnt = 1 , last = n - 1;
for(i = n - 1 ; ~i ; i -- )
{
if(r[i] > r[L]) return 0;
if(!cmp(i , last , L , R)) cnt ++ , last = i;
if(cnt > k) return 0;
}
return 1;
}
int main()
{
int i , j;
ll lp = 1 , rp = 0 , mid , ans;
scanf("%d%s" , &k , str) , n = strlen(str);
for(i = 0 ; i < n ; i ++ ) r[i] = str[i] - 'a' + 1;
n ++ , getsa() , n -- ;
for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;
for(i = 1 ; (1 << i) <= n ; i ++ )
for(j = (1 << i) ; j <= n ; j ++ )
height[j][i] = min(height[j][i - 1] , height[j - (1 << (i - 1))][i - 1]);
for(i = 1 ; i <= n ; i ++ ) rp += n - sa[i] - height[i][0];
while(lp <= rp)
{
mid = (lp + rp) >> 1 , query(mid);
if(judge()) ans = mid , rp = mid - 1;
else lp = mid + 1;
}
query(ans);
for(i = L ; i <= R ; i ++ ) putchar(str[i]);
return 0;
}