题目链接
https://codeforces.com/contest/1063/problem/F
题解
虽然本题有时间复杂度较高但非常好写的做法......
首先，若答案为 \(k\)，则一定存在一种最优方案，使得对于任意 \(i \in [1, k)\)，有 \(|t_i| = |t_{i + 1}| + 1\)，换句话说，第 \(i + 1\) 个字符串可以通过第 \(i\) 个字符串删掉首字符或尾字符得到。其正确性显然。
这样，我们可以记录 \(f_i\) 表示串 \(s\) 从 \(i\) 开始的的后缀，选择一个前缀作为串 \(t_1\) 可得到的最大的 \(k\)。求 \(f_i\) 显然可以二分，设二分的值为 \(v\)，由于最终得到的相邻两个字符串的长度差为 \(1\)，因此二分的值 \(v\) 即为当前以 \(s_i\) 开头的字符串 \(t_1\) 的长度。我们的任务是判断能否找到一个以 \(s_{i \sim i + v - 1}\) 删去首/尾字符作为前缀的后缀，使得该后缀对应的位置 \(p\) 满足 \(f_p \geq v - 1\)。
直接求难以入手，我们将问题转化一下，我们希望找到所有和从 \(i\) 或 \(i + 1\) 开始的后缀的 lcp 长度不小于 \(v - 1\) 的后缀对应位置的 \(f\) 的最大值。我们求出原串 \(s\) 的后缀数组后，合法的后缀对应的 \(\rm rank\) 一定是一段连续的且包含 \({\rm rank}_i\) 或 \({\rm rank}_{i + 1}\) 的区间。这样，我们就可以用线段树维护 \(f\)：把位置 \(p\) 对应的 \(f\) 值记录到线段树的 \({\rm rank}_p\) 位置，查询时直接区间查询最大值即可。合法后缀的 \(\rm rank\) 对应的区间也能通过二分得到，因此单次判断的时间复杂度为 \(O(\log n)\)，整个问题的时间复杂度即为 \(O(n \log^2 n)\)。
不过这并不是最优的时间复杂度。
首先给出结论：\(f_i \leq f_{i + 1} + 1\)。其正确性显然：由于 \(f_{i + 1}\) 较 \(f_i\) 而言，存在一种方案，第一个字符串只少了 \(s_i\) 一个字符，这样最多只会少一个字符串，故 \(f_{i + 1} \geq f_i - 1\)，即 \(f_i \leq f_{i + 1} + 1\)。
有了该结论后，我们就可以省去二分，对于位置 \(i\) 直接从 \(f_{i + 1} + 1\) 开始暴力判断，直到遇到第一个合法的值停止，将其作为 \(f_i\) 即可。这样，总时间复杂度就优化至了 \(O(n \log n)\)。
然而，上述做法始终回避了一个问题，那就是上述做法并没有使得字符串与字符串间不存在交。不过，使用 \(O(n \log n)\) 的做法能够很好地解决这一问题。注意到我们在判断位置 \(f_p = v\) 是否合法时，为了保证不存在交，我们希望只能查询到位置 \(p + v\) 及其之后的 \(f\) 值。由于当 \(p\) 固定时，我们枚举的 \(v\) 是从大到小的，又由于 \(f_p - f_{p + 1} \leq 1\)，因此我们希望查询到的合法区域的左端点也是单调不上升的。我们只需记录一个指针即可，时间复杂度依然是 \(O(n \log n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define rg register
template<typename T> inline bool checkMax(T& a, const T& b) {
return a < b ? a = b, true : false;
}
const int N = 5e5 + 10;
int n, c[N], x[N], y[N], sa[N], _rank[N], height[N], f[N][20], logv[N], g[N];
char s[N];
inline void get_sa(int m) {
for (rg int i = 0; i < n; ++i) {
++c[x[i] = s[i]];
}
for (rg int i = 1; i < m; ++i) {
c[i] += c[i - 1];
}
for (rg int i = n - 1; ~i; --i) {
sa[--c[x[i]]] = i;
}
for (rg int k = 1; k <= n; k <<= 1) {
int p = 0;
for (rg int i = n - 1; i >= n - k; --i) {
y[p++] = i;
}
for (rg int i = 0; i < n; ++i) {
if (sa[i] >= k) {
y[p++] = sa[i] - k;
}
}
fill(c, c + m, 0);
for (rg int i = 0; i < n; ++i) {
++c[x[y[i]]];
}
for (rg int i = 1; i < m; ++i) {
c[i] += c[i - 1];
}
for (rg int i = n - 1; ~i; --i) {
sa[--c[x[y[i]]]] = y[i];
}
swap(x, y);
p = 1, x[sa[0]] = 0;
for (rg int i = 1; i < n; ++i) {
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p - 1 : p++;
}
if (p >= n) {
break;
}
m = p;
}
}
inline void get_height() {
for (rg int i = 0; i < n; ++i) {
_rank[sa[i]] = i;
}
int k = 0;
for (rg int i = 0; i < n; ++i) {
k -= k ? 1 : 0;
if (!_rank[i]) {
continue;
}
int j = sa[_rank[i] - 1];
for (; s[i + k] == s[j + k]; ++k);
height[_rank[i]] = k;
}
for (rg int i = 0; i < n; ++i) {
f[i][0] = height[i];
}
for (rg int i = 2; i <= n; ++i) {
logv[i] = logv[i >> 1] + 1;
}
for (rg int j = 1; (1 << j) <= n; ++j) {
for (rg int i = 0; i + (1 << j) - 1 < n; ++i) {
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
inline int query(int x, int y) {
x = _rank[x];
y = _rank[y];
if (x > y) {
swap(x, y);
}
++x;
int k = logv[y - x + 1];
return min(f[x][k], f[y - (1 << k) + 1][k]);
}
#define lo (o<<1)
#define ro (o<<1|1)
int maxv[N << 2];
inline void modify(int l, int r, int o, int p, int v) {
if (l == r) {
maxv[o] = v;
} else {
int mid = l + r >> 1;
(p <= mid) ? modify(l, mid, lo, p, v) : modify(mid + 1, r, ro, p, v);
maxv[o] = max(maxv[lo], maxv[ro]);
}
}
inline int query(int l, int r, int o, int ql, int qr) {
if (ql <= l && r <= qr) {
return maxv[o];
} else {
int mid = l + r >> 1, res = 0;
if (ql <= mid) {
checkMax(res, query(l, mid, lo, ql, qr));
} if (qr > mid) {
checkMax(res, query(mid + 1, r, ro, ql, qr));
}
return res;
}
}
inline bool binary_search(int p, int len) {
int l = 0, r = _rank[p], ql, qr;
while (l ^ r) {
int mid = l + r >> 1;
if (query(sa[mid], p) >= len) {
r = mid;
} else {
l = mid + 1;
}
}
ql = l;
l = _rank[p], r = n - 1;
while (l ^ r) {
int mid = (l + r >> 1) + 1;
if (query(sa[mid], p) >= len) {
l = mid;
} else {
r = mid - 1;
}
}
qr = l;
return query(0, n - 1, 1, ql, qr) >= len;
}
inline bool check(int p, int len) {
--len;
return binary_search(p, len) | binary_search(p + 1, len);
}
int main() {
scanf("%d%s", &n, s);
get_sa('z' + 1);
get_height();
int ans = 0;
for (rg int i = n - 1, p = n - 1, last_val = 0; ~i; --i) {
for (++last_val; !check(i, last_val); --last_val, modify(0, n - 1, 1, _rank[p], g[p]), --p);
checkMax(ans, g[i] = last_val);
}
printf("%d\n", ans);
return 0;
}