#include <cstdio>
#include <cstring>
#include <algorithm>
#define rank rank2

using namespace std;

char s[400005];
int wx[400005], wy[400005], c[400005];
int sa[400005];

void build(int n, int m) {
    int *x = wx, *y = wy;

    for (int i = 0; i < n; i++)
        c[s[i]]++;

    for (int i = 1; i < m; i++)
        c[i] += c[i - 1];

    for (int i = n - 1; i >= 0; i--)
        sa[--c[x[i] = s[i]]] = i;

    int p;

    for (int j = 1; p < n; j <<= 1) {
        p = 0;

        for (int i = n - j; i < n; i++)
            y[p++] = i;

        for (int i = 0; i < n; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;

        for (int i = 0; i < m; i++)
            c[i] = 0;

        for (int i = 0; i < n; i++)
            c[x[y[i]]]++;

        for (int i = 1; i < m; i++)
            c[i] += c[i - 1];

        for (int i = n - 1; i >= 0; i--)
            sa[--c[x[y[i]]]] = y[i];

        swap(x, y);
        x[sa[0]] = 0;
        p = 1;

        for (int i = 1; i < n; i++)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) ? p - 1 : p++;

        m = p;
    }
}

int rank[400005], h[400005];

void getheight(int n) {
    for (int i = 0; i < n; i++)
        rank[sa[i]] = i;

    int k = 0;

    for (int i = 0; i < n; i++) {
        if (k)
            k--;

        if (!rank[i])
            continue;

        int j = sa[rank[i] - 1];

        while (s[i + k] == s[j + k])
            k++;

        h[rank[i]] = k;
    }
}

int d[400005];

int solve(int l, int r, int n) {
    for (int i = 0; i < n; i++)
        d[i] = n;

    d[l] = r - l + 1;

    for (int i = rank[l] + 1; i < n; i++) {
        d[sa[i]] = min(d[sa[i - 1]], h[i]);

        if (!d[sa[i]])
            return n;
    }

    int ans = 0, rx = n;

    for (int i = 0; i < n; i++) {
        if (rx < i) {
            ans++;
            rx = n;
        }

        rx = min(rx, i + d[i] - 1);
    }

    ans++;
    return ans;
}

int main() {
    int k;
    scanf("%d%s", &k, s);
    int n = strlen(s);
    build(n, 128);
    getheight(n);
    int l = 0, r = n - 1;

    while (l < r) {
        int m = ((l + r) >> 1);

        if (solve(sa[m], n - 1, n) <= k)
            r = m;
        else
            l = m + 1;
    }

    int p = sa[l];
    l = 1;
    r = n - p;

    while (l < r) {
        int m = ((l + r) >> 1);

        if (solve(p, p + m - 1, n) <= k)
            r = m;
        else
            l = m + 1;
    }

    for (int i = p; i < p + l; i++)
        putchar(s[i]);

    putchar('\n');
    return 0;
}

字符串分段最小最大字典序问题题解

题目分析

给定长度为 $n$ 的字符串和整数 $k$，需将字符串划分为 $k$ 个连续非空子串。对于每段，定义 $C_i$ 为该段中字典序最大的子串（子串为连续字符序列），目标是找到所有划分方案中，$C_1, C_2, ..., C_k$ 中字典序最大的那个的最小值。

算法思路

核心观察

1. 最大子串的性质：一段字符串中字典序最大的子串一定是该段的某个后缀（因为更长的后缀在字典序比较中具有天然优势，若前缀相同则更长的串更大）。
2. 二分答案思路：问题可转化为“找到最小的字符串 $T$，使得存在一种 $k$ 段划分，每段的最大子串（后缀）均不大于 $T$”。
3. 后缀数组辅助：利用后缀数组将所有后缀按字典序排序，通过二分查找高效定位候选 $T$。

算法流程

1. 构建后缀数组与高度数组：
   后缀数组 sa 记录所有后缀的起始位置按字典序排序的结果（sa[i] 表示排名第 $i$ 的后缀的起始索引）；高度数组 h 记录相邻排名后缀的最长公共前缀（LCP）长度，用于快速比较后缀间的字典序。

2. 二分查找候选后缀：
   在后缀数组中二分查找最小的排名 $m$，使得以 sa[m] 为起始的后缀 $T$ 满足：字符串可划分为 $\leq k$ 段，每段的最大子串均不大于 $T$。

3. 确定最短有效长度：
   对于找到的候选后缀，进一步二分其长度，找到最短的 $T'$（$T$ 的前缀），仍满足划分条件。

关键函数解析

1. 后缀数组构建（build 函数）

采用倍增算法构建后缀数组：

• 按字符 ASCII 码初始化排序，再通过倍增长度（$2^j$）迭代排序，利用前一轮结果优化当前轮排序。
• 时间复杂度 $O(n \log n)$，适配 $n \leq 4 \times 10^5$ 的数据范围。

2. 高度数组计算（getheight 函数）

高度数组 h[i] 表示排名第 $i$ 和第 $i-1$ 的后缀的 LCP 长度：

• 利用排名数组 rank（rank[i] 表示起始于 $i$ 的后缀的排名），通过递推计算 $h$，时间复杂度 $O(n)$。

3. 可行性判断（solve 函数）

判断以 $s[l..r]$ 为候选 $T$ 时，能否将字符串划分为 $\leq k$ 段：

• 计算 d[i]：d[i] 表示从 $i$ 开始的子串中，不大于 $T$ 的最大长度（通过高度数组和后缀排名关系快速计算）。
• 贪心划分：从左到右遍历字符串，每次尽可能延伸当前段（最大长度为 d[i]），统计所需段数。若段数 $\leq k$ 则可行。

4. 二分查找过程

• 第一阶段：在后缀数组中二分排名 $m$，找到最小的 $m$ 使得 sa[m] 对应的后缀作为 $T$ 可行。
• 第二阶段：对找到的后缀，二分其长度，确定最短有效 $T$。

算法标签

• 后缀数组
• 二分查找
• 贪心算法
• 字符串字典序
• 倍增算法

代码解析

变量说明

核心逻辑

1. 后缀数组与高度数组构建：为后续字典序比较和 LCP 计算奠定基础。
2. 二分排名找候选后缀：通过 solve 函数验证可行性，定位最小的有效排名。
3. 二分长度找最短 $T$：在候选后缀基础上，确定最短的有效前缀，即为答案。

时间复杂度

• 后缀数组构建：$O(n \log n)$
• 高度数组计算：$O(n)$
• 二分查找（两轮）：每轮 $O(\log n)$，每轮验证（solve 函数）$O(n)$，总 $O(n \log n)$
• 整体时间复杂度：$O(n \log n)$，可处理 $n \leq 4 \times 10^5$ 的数据。

示例解析

以样例 1（k=2，字符串 "aba"）为例：

• 后缀数组排序结果为：sa[0]=1（后缀 "ba"）、sa[1]=2（后缀 "a"）、sa[2]=0（后缀 "aba"）。
• 二分找到排名 $m=0$（后缀 "ba"），验证可行（划分 "a|ba"，两段最大子串为 "a" 和 "ba"，最大值为 "ba"）。
• 进一步确定最短长度为 1（即 "b"），满足划分条件，故输出 "b"。

通过后缀数组高效处理字典序比较，结合二分查找和贪心划分，成功解决了字符串分段的最小最大字典序问题。