本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-12 10:06:08
考虑说直接贪心不太能做，所以考虑 DP。
考虑说我们选后缀比前缀容易，所以我们倒着 DP。
考虑说我们如果设 $f_{i,j}$ 表示分了后 $i$ 个 $j$ 段是否可行，我们发现 $i,j$ 从 $f_{k,j - 1}$ 转移，但我们需要枚举 $i,j,k$ 还有 $k$ 最后一段的长度，感觉不太好优化。
考虑到原来的 DP 主要关心最后一段多长，所以我们考虑设 $f_{i, j}$ 表示 $[i, n]$ 这段后缀，最后一段为 $[i,j]$ 最长的段数是多少。
然后我们枚举 $i, j$，然后考虑用 SA 求出来 $[i, n]$ 和 $[j + 1, n]$ 的最长公共前缀设为 $s$，那么就看如果 $[i,i + \min(lcp, j - i + 1)]$ 这段是否小于 $[j + 1, j + 1 + \min(lcp, j - i + 1)]$，如果是的话，那么 $f_{i,j}$ 就是 $\max_{k=j + 1 + \min(lcp, j - i + 1)} ^ {n} f_{j + 1, k}$，然后发现是后缀 $\max$，于是再开一个数组维护即可。
#include <bits\/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, p;
char s[5010];
pair<int, int> f[5010][5010];
pair<int, int> g[5010][5010];
int st[16][N], log_2[N];
int sa[N], rk[N], ork[N], id[N], cnt[N];
int queryM(int l, int r) {
int L = log_2[r - l + 1];
return min(st[L][l], st[L][r - (1 << L) + 1]);
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
m = 255;
for (int i = 1; i <= n; ++i) cnt[rk[i] = s[i]]++;
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
for (int w = 1; ; w <<= 1, m = p) {
int cc = 0;
for (int i = n - w + 1; i <= n; ++i) id[++cc] = i;
for (int i = 1; i <= n; ++i)
if (sa[i] > w) id[++cc] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) cnt[rk[i]]++;
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];
memcpy(ork, rk, sizeof(ork));
p = 0;
for (int i = 1; i <= n; ++i)
if (ork[sa[i]] == ork[sa[i - 1]] && ork[sa[i] + w] == ork[sa[i - 1] + w])
rk[sa[i]] = p;
else
rk[sa[i]] = ++p;
if (p == n) break;
}
for (int i = 1, k = 1; i <= n; ++i) {
if (!rk[i]) continue;
if (k) --k;
\/\/ cout << sa[rk[i] - 1] << ' ' << i << ' ' << rk[i] << ' ' << sa[rk[i]] << ' ' << sa[rk[i] - 1] << ' ' << sa[i] << endl;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
st[0][rk[i]] = k;
}
for (int i = 1; i <= 15; ++i)
for (int j = 1; j <= n; ++j)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
log_2[1] = 0;
for (int i = 2; i <= n; ++i) log_2[i] = log_2[i >> 1] + 1;
for (int i = n; i >= 1; --i) {
for (int j = i; j <= n; ++j) {
if (j == n) {
f[i][j] = {1, n + 1};
break;
}
int l = rk[i], r = rk[j + 1];
if (l > r) swap(l, r);
int lcp = min(queryM(l + 1, r), j - i + 1);
if (lcp == n - j) continue;
if (lcp >= j - i + 1) {
if (g[j + 1][j + j - i + 2].first + 1 > f[i][j].first)
f[i][j] = {g[j + 1][j + j - i + 2].first + 1, g[j + 1][j + j - i + 2].second};
} else {
if (s[i + lcp] < s[j + lcp + 1]) {
if (g[j + 1][j + lcp + 1].first + 1 > f[i][j].first)
f[i][j] = {g[j + 1][j + lcp + 1].first + 1, g[j + 1][j + lcp + 1].second};
}
}
\/\/ cout << i << ' ' << j << ' ' << lcp << ' ' << f[i][j].first << "----" << ' ' << j + lcp + 1 << ' ' << g[j + 1][j + lcp + 1].first << endl;
}
for (int j = n; j >= i; --j) {
g[i][j] = max(g[i][j + 1], {f[i][j].first, j});
}
}
int ans = 0, id = 0;
for (int i = 1; i <= n; ++i) {
if (f[1][i].first > ans) {
ans = f[1][i].first;
id = i;
}
}
printf("%d\n", ans);
int l = 1;
while (id <= n) {
for (int i = l; i <= id; ++i) putchar(s[i]);
putchar('\n');
int tid = id;
id = f[l][id].second;
l = tid + 1;
}
return 0;
}
鲁ICP备2025150228号