不知道后缀数组的请退回去！
题面：
很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。现在他想找一个最优的分法让“魔力串”字典序最小。
第一行一个整数 k，k≤15
接下来一个长度不超过 10^5的字符串 s。
输出一行，表示字典序最小的“魔力串”。
2
ababa
ba
分成aba和ba两个串，其中字典序最大的子串为ba
看到让最大的最小我们就想到二分答案，二分答案在原字符串的所有不同子串中的排名。知道了排名，我们用后缀数组就很好求出答案串是什么(记录其在原串中的起始位置和结束位置)，具体方法见代码。
这里还有一点要考虑的是二分的上界也就是子串的个数。其实这很好求就是∑n-sa[i]+1-height[i[。毕竟所有的子串都是一个后缀的前缀，对于一个后缀sa[i]，他有n-sa[i]+1个前缀，但是有height[i]个前缀与前面的重复，已经算过了，就得减掉。
然后我们来考虑如何判定。这里我默认大家都会求LCP(LCP(i, j)=min{height[k]}(rank[i]<k<=rank[j])，然后用ST表nlogn预处理，O(1)时间内求出LCP)。记录一个cut=i代表你上次在i-1和i之间切了一刀，令cut的初值为n+1。再记录一个cnt代表切了多少次，如果cnt>=k则不成立(这里注意切了cnt到右cnt+1个块，所以是>=)。每次判定先求出当且串的起始和结束位置记为L, R，然后再从后往前枚举后缀i，求出i和L的LCP。若LCP==0，则判断s[L]和s[i]的大小关系，若s[i]>s[L]则返回false(根据题目要求s[L…R]应是一个快内最大的)。求min{LCP, cut - i, R - L + 1}。若cut-i最小，则说明上次剪的地方到现在这一段都是相同的(<LCP)或者比当前串还短(<R-L+1)，此时这个位置一定不需要剪，直接continue。若R-L+1最小或者LCP最小且s[L+LCP]<s[i+LCP]时我们就需要分块。令cut = i + 1，cnt++，然后再判断cnt与k的关系即可。
上代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 100010; ll k; ll n, m; ll sa[N], rnk[N], v1[N], v2[N], sum[N], height[N]; ll st[N][21]; char s[N]; bool cmp(ll *t, ll a, ll b, ll l) { return t[a] == t[b] && t[a + l] == t[b + l]; } void da() { ll i, j, p = 0; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[rnk[i] = s[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i - 1]; for (i = n; i >= 1; i--) sa[sum[rnk[i]]--] = i; for (j = 1; j <= n; j *= 2, m = p) { for (p = 0, i = n - j + 1; i <= n; i++) v2[++p] = i; for (i = 1; i <= n; i++) if (sa[i] > j) v2[++p] = sa[i] - j; for (i = 1; i <= n; i++) v1[i] = rnk[v2[i]]; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[v1[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i - 1]; for (i = n; i >= 1; i--) sa[sum[v1[i]]--] = v2[i]; for (swap(rnk, v2), rnk[sa[1]] = 1, p = 2, i = 2; i <= n; i++) { rnk[sa[i]] = cmp(v2, sa[i - 1], sa[i], j) ? p - 1 : p++; } } } void calheight() { ll i, j, p = 0; for (i = 1; i <= n; i++) { if (p) p--; j = sa[rnk[i] - 1]; while (s[i + p] == s[j + p]) p++; height[rnk[i]] = p; } } void st_pre() { for (ll i = 1; i <= n; i++) st[i][0] = height[i]; for (ll j = 1; j <= 20; j++) { for (ll i = 1; i <= n; i++) { if (i + (1 << (j - 1)) > n) break; st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } } ll LCP(ll l, ll r) { if (l == r) return n - sa[l] + 1; if (l > r) swap(l, r); l++; ll kk = log(r - l + 1) / log(2); return min(st[l][kk], st[r - (1 << kk) + 1][kk]); } ll pos_l, pos_r, ans_l, ans_r; void get_string(ll mid) { for (ll i = 1; i <= n; i++) { ll tmp = n - sa[i] - height[i] + 1; if (mid > tmp) { mid -= tmp; } else { pos_l = sa[i]; pos_r = sa[i] + height[i] - 1 + mid; return; } } } bool check() { for (ll i = n, cut = n + 1, cnt = 0; i >= 1; i--) { ll lcp = LCP(rnk[pos_l], rnk[i]); if (lcp == 0 && s[i] > s[pos_l]) return false; lcp = min(lcp, min(pos_r - pos_l + 1, cut - i)); if (lcp == cut - i) continue; if (lcp == pos_r - pos_l + 1 || s[i + lcp] > s[pos_l + lcp]) { cnt++; cut = i + 1; if (cnt > k) return false; } } return true; } int main() { scanf("%lld%s", &k, s + 1); k--; n = strlen(s + 1); m = 200; da(); calheight(); st_pre(); ll l = 1, r = 0; for (ll i = 1; i <= n; i++) { r += n - sa[i] - height[i] + 1; } while (l <= r) { ll mid = (l + r) >> 1; get_string(mid); if (check()) { ans_l = pos_l; ans_r = pos_r; r = mid - 1; } else { l = mid + 1; } } for (ll i = ans_l; i <= ans_r; i++) { cout << s[i]; } return 0; }
原文：https://www.cnblogs.com/zcr-blog/p/12246282.html