H. 缺失的分隔符 详细题解

问题重述

给定一个字符串 $S$（$|S|\le 5000$），它是由一个字典中的单词按字典序升序拼接而成，单词之间没有分隔符。需要将 $S$ 分割成若干个互不相同的单词，且这些单词按字典序严格递增（因为原字典已排序且单词互异）。要求最大化单词个数，并输出任意一种合法分割方案。

---

动态规划思路

贪心法不可行，使用区间 DP。

状态定义

设 $DP[x][y]$ 表示：已经构造了从 $S$ 开头到位置 $y$ 的单词，且最后一个单词是子串 $S[x..y]$（闭区间）时，从位置 $y+1$ 开始最多还能再构造出多少个单词（包括当前已构造的？通常定义 $DP[x][y]$ 为“从当前状态开始，后续能构造的最大单词数”）。
更常见的实现是：$DP[x][y]$ 表示以 $S[x..y]$ 作为最后一个单词，从 $y+1$ 到末尾能形成的最大单词数（包括后续所有单词，但不包括 $S[x..y]$ 本身）。这样最终答案需要在起始处加上第一个单词。

但为了方便转移，我们定义 $DP[x][y]$ 表示已经完成了以 $S[x..y]$ 结尾的单词，从下一个位置开始还能形成的最多单词数。那么初始时，我们需要枚举第一个单词 $S[0..y]$，然后答案就是 $1 + DP[0][y]$ 的最大值。

不过标程中的表述略有不同，我们按照官方解法来：

设 $DP[x][y]$ 表示如果最后一个构造的单词是子串 $S[x..y]$，那么之后还能再构造出多少个单词。

因此转移时，我们要从 $y+1$ 开始选取下一个单词 $S[y+1..z]$，并且要保证 $S[y+1..z]$ 字典序大于 $S[x..y]$。然后状态转移到 $DP[y+1][z]$，并加上 $1$（当前这个新单词）。所以：

$$DP[x][y] = \max_{z} \big( 1 + DP[y+1][z] \big)$$

其中 $z$ 必须满足 $S[y+1..z] > S[x..y]$ 且 $z$ 在 $[y+1, n]$ 内。

边界条件：如果 $y = n$（即已经处理完整个字符串），则 $DP[x][n] = 0$（没有后续单词）。

---

如何找到可行的 $z$

对于固定的 $x,y$，我们要找到所有 $z$ 使得 $S[y+1..z] > S[x..y]$。关键观察：

• 如果 $S[y+1..]$ 的最长公共前缀（LCP）与 $S[x..y]$ 的长度等于 $len = y-x+1$，即 $S[x..y]$ 是 $S[y+1..]$ 的前缀，那么任何比 $S[x..y]$ 更长的子串 $S[y+1..z]$（$z \ge y+len$）都一定大于 $S[x..y]$，因为长的那个串在相同前缀后还有额外字符。此时第一个可行的 $z$ 是 $y+len$。
• 否则，设 $l = \text{LCP}(S[x..y], S[y+1..])$，即从 $x$ 和 $y+1$ 开始的最长公共前缀长度，且 $l < len$。那么 $S[x+l] \neq S[y+1+l]$。如果 $S[y+1+l] > S[x+l]$，则子串 $S[y+1..z]$ 只要长度 $\ge l+1$ 就大于 $S[x..y]$；否则，任何以 $S[y+1..]$ 开头的子串都不可能大于 $S[x..y]$（因为第一个不同字符更小），因此不存在可行的 $z$。

因此，只需找到第一个可行的 $z$，记为 $firstZ$。之后所有 $z \ge firstZ$ 也都是可行的（因为增加长度不会改变字典序比较的结果，只要之前已经大于）。所以，我们需要计算的是：

$$DP[x][y] = \max_{z \ge firstZ} \big( 1 + DP[y+1][z] \big) $$

这等价于 $1 + \max_{z \ge firstZ} DP[y+1][z]$。

---

快速计算 LCP

为了得到 $firstZ$，我们需要计算 $\text{LCP}(S[x..y], S[y+1..])$，即后缀 $S[x..]$ 和后缀 $S[y+1..]$ 的最长公共前缀长度，但不能超过 $len$。

定义辅助数组 $LCPS[p][q]$ 表示后缀 $S[p..]$ 和 $S[q..]$ 的最长公共前缀长度。显然有递推：

$$LCPS[p][q] = \begin{cases} 0 & \text{if } S[p] \neq S[q] \\ 1 + LCPS[p+1][q+1] & \text{if } S[p] = S[q] \end{cases}$$

边界：当 $p=n$ 或 $q=n$ 时 $LCPS[p][q]=0$。

那么，$S[x..y]$ 与 $S[y+1..]$ 的 LCP 长度就是 $\min(LCPS[x][y+1],\ y-x+1)$。因为 $LCPS[x][y+1]$ 可能超过 $len$，需要截断。

这样我们就能在 $O(1)$ 时间内得到第一个不同字符的位置，从而确定 $firstZ$：

• 设 $lcp = \min(LCPS[x][y+1],\ y-x+1)$。
• 如果 $lcp = y-x+1$（即 $S[x..y]$ 是 $S[y+1..]$ 的前缀），则第一个可行的 $z$ 为 $y + (y-x+1)$，即 $z = 2y - x + 1$。
• 否则，比较 $S[x+lcp]$ 和 $S[y+1+lcp]$：
  • 若 $S[y+1+lcp] > S[x+lcp]$，则第一个可行的 $z$ 为 $y+1+lcp$。
  • 否则，不存在可行的 $z$（$DP[x][y]$ 为 $-\infty$）。

---

后缀最大值优化

对于每个固定的 $y$，我们需要快速查询 $\max_{z \ge t} DP[y+1][z]$。我们可以预处理一个后缀最大值数组 $sufMax[y][p]$，其中 $sufMax[y][p] = \max_{z \ge p} DP[y][z]$。这样在转移时，$DP[x][y] = 1 + sufMax[y+1][firstZ]$。

由于 $x,y$ 共有 $O(n^2)$ 个状态，每个转移 $O(1)$，总复杂度 $O(n^2)$。

---

回溯构造答案

计算完所有 $DP[x][y]$ 后，我们从开头开始构造。首先枚举第一个单词 $S[0..y]$，选择使 $1+DP[0][y]$ 最大的 $y$（若有多个任选）。然后递归地选择下一个单词：已知当前单词为 $S[x..y]$，那么下一个单词的起始位置为 $y+1$，我们需要选择一个 $z$ 使得 $DP[y+1][z]$ 达到最大值，且 $z$ 是可行的（即满足字典序条件）。由于我们记录了后缀最大值，可以知道最佳的 $z$ 就是满足 $DP[y+1][z] = sufMax[y+1][firstZ]$ 的任意 $z$（通常取最小 $z$ 即可）。依次输出每个单词。

---

复杂度与实现细节

• 预计算 $LCPS$：$O(n^2)$。
• 预计算后缀最大值：$O(n^2)$。
• DP 本身也是 $O(n^2)$。
• 回溯：$O(n)$。
• 总时间复杂度 $O(|S|^2)$，空间 $O(|S|^2)$，对于 $n\le 5000$ 可接受（约 $25\times 10^6$ 个状态，每个状态存储整数，内存约 $100$ MB，需要注意优化）。

---

参考代码框架

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int n = S.size();
    // LCPS[p][q] : 后缀 S[p..] 和 S[q..] 的 LCP 长度
    vector<vector<int>> lcps(n+2, vector<int>(n+2, 0));
    for (int p = n-1; p >= 0; --p) {
        for (int q = n-1; q >= 0; --q) {
            if (S[p] == S[q]) lcps[p][q] = 1 + lcps[p+1][q+1];
        }
    }
    // dp[x][y] : 最后一个单词为 S[x..y] 时，之后最多还能再构造多少个单词
    // 为了方便，我们定义 dp 值为 -1 表示不可能
    vector<vector<int>> dp(n+2, vector<int>(n+2, -1));
    vector<vector<int>> sufMax(n+2, vector<int>(n+2, -1));
    // 边界：y == n 时，没有后续，dp[x][n] = 0
    for (int x = 0; x <= n; ++x) dp[x][n] = 0;
    // 从后向前计算
    for (int y = n-1; y >= 0; --y) {
        // 先计算 sufMax[y+1][*]（需要后一行已经算好）
        for (int z = n; z >= 0; --z) {
            sufMax[y+1][z] = max(dp[y+1][z], (z+1 <= n ? sufMax[y+1][z+1] : -1));
        }
        for (int x = y; x >= 0; --x) {
            int len = y - x + 1;
            int l = min(lcps[x][y+1], len);
            if (l == len) {
                // S[x..y] 是 S[y+1..] 的前缀
                int firstZ = y + len;
                if (firstZ <= n) {
                    int best = sufMax[y+1][firstZ];
                    if (best != -1) dp[x][y] = best + 1;
                }
            } else {
                if (S[x+l] < S[y+1+l]) {
                    int firstZ = y + 1 + l;
                    if (firstZ <= n) {
                        int best = sufMax[y+1][firstZ];
                        if (best != -1) dp[x][y] = best + 1;
                    }
                }
            }
        }
    }
    // 找出第一个单词的最佳起始 y
    int bestY = -1, bestCnt = -1;
    for (int y = 0; y < n; ++y) {
        if (dp[0][y] != -1) {
            int cnt = 1 + dp[0][y];
            if (cnt > bestCnt) {
                bestCnt = cnt;
                bestY = y;
            }
        }
    }
    // 回溯输出
    vector<string> words;
    int x = 0, y = bestY;
    while (y < n) {
        words.push_back(S.substr(x, y-x+1));
        // 找下一个单词
        int nx = y+1;
        int len = y-x+1;
        int l = min(lcps[x][y+1], len);
        int firstZ;
        if (l == len) firstZ = y + len;
        else firstZ = y + 1 + l;
        // 在 nx 行中，取最佳的 z 使得 dp[nx][z] 等于 sufMax[nx][firstZ]
        int target = sufMax[nx][firstZ];
        int nz = -1;
        for (int z = firstZ; z <= n; ++z) {
            if (dp[nx][z] == target) {
                nz = z;
                break;
            }
        }
        x = nx;
        y = nz;
    }
    cout << bestCnt << '\n';
    for (const string& w : words) cout << w << '\n';
    return 0;
}

---

总结

本题的核心是利用 $LCPS$ 预计算任意两个后缀的 LCP，从而在 $O(1)$ 内判断字典序关系，并用后缀最大值优化 DP 转移。最终得到 $O(|S|^2)$ 的解法，完美解决 $|S| \le 5000$ 的规模。