P6095 [JSOI2015]串分割

· · 题解

P6095 [JSOI2015]串分割

因为字符不含 0，所以贪心让最大位数最小。答案串长度 L = \left \lceil \dfrac n k \right\rceil。

答案满足可二分性。我们二分答案在后缀数组中的排名。破环成链，枚举 L 个起始点并判断是否可行。假设当前匹配到 i，若 s[i, i + L - 1] 的排名不大于二分的答案，那么就匹配 L 位，否则匹配 L - 1 位。若进行 k 次匹配后总匹配位数不小于 n 则可行。

若可匹配 L 位时匹配 L - 1 位，则下一次最多匹配 L 位，这与首先匹配 L 位时下一次匹配的最劣情况，即匹配 L - 1 位，效果相同。因此贪心正确。

进一步地，比较两个长度为 L 的字符串时，我们不需要求 LCP 并比较下一个字符。可直接比较它们对应的后缀。问题在于也许 s[i, i + L - 1] 和 s[j, j + L - 1] 相等，其中 j 是排名为当前二分值的后缀开始位置，但 suf_i > suf_j，这使得我们认为只能匹配 L - 1 位而非 L 位。

但其实没有关系，因为若 s[j, j + L - 1] 作为答案串可行，则二分排名最大的以 s[j, j + L - 1] 作为前缀的后缀时必然可行。

时间复杂度 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 4e5 + 5;
int n, k, len;
char s[N];
int rk[N], ork[N], sa[N], buc[N], id[N];
bool cmp(int a, int b, int w) {return ork[a] == ork[b] && ork[a + w] == ork[b + w];}
void build() {
  int m = 1 << 7, p = 0;
  for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
  for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
  for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
  for(int w = 1; ; w <<= 1, m = p, p = 0) {
    for(int i = n - w + 1; i <= n; i++) id[++p] = i;
    for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
    memset(buc, 0, sizeof(buc));
    memcpy(ork, rk, sizeof(rk));
    p = 0;
    for(int i = 1; i <= n; i++) buc[rk[i]]++;
    for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
    for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];
    for(int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
    if(p == n) break;
  }
}
bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  cin >> n >> k >> s + 1, len = (n - 1) / k + 1;
  for(int i = 1; i <= n; i++) s[i + n] = s[i];
  n <<= 1, build();
  int l = 1, r = n, m = n >> 1;
  while(l < r) {
    int mid = l + r >> 1, ok = 0;
    for(int i = 1; i <= len; i++) {
      int cur = 0;
      for(int j = 1; j <= k; j++) {
        int p = (i + cur - 1) % m + 1;
        if(rk[p] <= mid) cur += len;
        else cur += len - 1;
      }
      ok |= cur >= m;
    }
    if(ok) r = mid;
    else l = mid + 1;
  }
  for(int i = 0; i < len; i++) cout << s[sa[l] + i];
  return cerr << "Time: " << clock() << "\n", 0;
}
/*
2022/7/2
start coding at 18:24
finish debugging at 18:36
*/