题目链接：Codeforces 700E
Bomboslav 成立了一个品牌代理商，正在帮助公司创建商标和广告。就这个问题而言，公司的广告应该是其名称的非空子串。
有时，公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次（允许重叠），那么认为广告 $A$ 比 $B$ 更酷。
你得到了某个公司的名字 $w$，你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。
数据范围：$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。
Solution
首先将问题化简：求出字符串序列 $s_i$ 的最长长度 $k$，满足如下约束条件：
- 字符串 $s_i$ 是 $s_{i - 1}$ 的子串，且 $s_i$ 在 $s_{i - 1}$ 中作为子串出现了至少 $2$ 次。
- $s_1 = w$。
首先假设我们已经知道了如何判断字符串 $A$ 是否在 $B$ 中出现了 $2$ 次，那么这个问题可以直接在 $\text{Parent}$ 树上进行 $\text{DP}$ 了。
考虑某个串 $A$ 在其非 $\text{Parent}$ 树上的子树中的节点对应的串 $B$ 中出现了 $2$ 次，那么 $B$ 一定是由 $A$ 子树内的某个串加上一个后缀得到的，这样子显然不优。因此只需要考虑在 $\text{Parent}$ 树上从上往下转移。
我们对原串 $w$ 建立后缀自动机，如果字符串 $A$ 在 $B$ 中出现了 $2$ 次，那么在 $B$ 的所有 $endpos$ 位置的串 $B'$ 中都出现了 $2$ 次，因此对于字符串 $B$ 我们只需要对于 $\text{SAM}$ 上每个状态记录任意一个 $endpos$ 就行了。
但是对于字符串 $A$，我们需要维护其所有 $endpos$，以便与 $B$ 串进行匹配。我们可以用线段树维护每个状态的 $endpos$ 集合，从下往上采用线段树合并的方法对状态进行合并。
记状态 $i$ 的任意一个 $endpos$ 为 $pos(i)$，状态 $i$ 的最长后缀长度为 $len(i)$。
考虑如何进行判断。对于状态 $i$，我们尝试判断其祖先状态 $j$ 是否在 $i$ 中出现了至少 $2$ 次。那么 $j$ 的 $endpos$ 集合一定要在 $[pos(i) - len(i) + len(j), pos(i)]$ 区间内出现至少 $2$ 次。
又因为 $j$ 一定是 $i$ 的真后缀，那么 $endpos$ 集合中一定有 $pos(i)$，故只需要判断 $j$ 的 $endpos$ 集合是否在区间 $[pos(i) - len(i) + len(j), pos(i) - 1]$ 内出现过。
考虑如何进行转移。定义 $f(i)$ 表示到状态 $i$ 的最大值。对于每个状态 $i$，我们需要枚举其在 $\text{Parent}$ 树上的所有祖先，如果某个状态 $j$ 合法，那么用 $f(j) + 1$ 更新 $f(i)$；如果不存在合法祖先状态，那么 $f(i)$ 直接继承 $f(link(i))$（$link(i)$ 表示 $i$ 的后缀链接）的值。答案为 $\max\{f(i)\}$。
直接转移的复杂度是不对的。注意到从初始状态某个状态 $i$ 上的 $f$ 值是单调不降的。于是我们记录 $top(i)$ 表示 $i$ 到初始状态中（包括 $i$ 本身），所有 $f$ 值最大且 $len$ 最小的状态（其中 $len$ 最小是为了贪心地选择更小的，使得更有可能匹配成功）。那么直接判断 $top(link(i))$ 是否合法并更新 $f(i)$ 的值。
时间复杂度：$\mathcal O(n \log n)$。
Code
#include <cstdio>
#include <algorithm>
const int N = 2e5 + 5;
int n, rt[N << 1], bin[N], t[N << 1], f[N << 1], top[N << 1];
char s[N];
template <int MAX, int S>
struct SAM {
static const int N = MAX << 1;
int tot, lst, len[N], lnk[N], pos[N], nxt[N][S];
SAM() {
lnk[tot = lst = 0] = -1;
}
void insert(int x, int i) {
int cur = ++tot;
len[cur] = len[lst] + 1;
pos[cur] = i;
int p = lst;
for (; ~p && !nxt[p][x]; p = lnk[p]) nxt[p][x] = cur;
if (p == -1) {
lnk[cur] = 0;
} else {
int q = nxt[p][x];
if (len[q] == len[p] + 1) {
lnk[cur] = q;
} else {
int c = ++tot;
len[c] = len[p] + 1;
lnk[c] = lnk[q];
pos[c] = pos[q];
std::copy(nxt[q], nxt[q] + S, nxt[c]);
for (; ~p && nxt[p][x] == q; p = lnk[p]) nxt[p][x] = c;
lnk[cur] = lnk[q] = c;
}
}
lst = cur;
}
};
template <int MAX>
struct SegmentTree {
static const int N = MAX * 20;
int tot, ls[N], rs[N];
int merge(int p1, int p2) {
if (!p1 || !p2) return p1 | p2;
int p = ++tot;
ls[p] = merge(ls[p1], ls[p2]);
rs[p] = merge(rs[p1], rs[p2]);
return p;
}
void modify(int &p, int l, int r, int x) {
p = ++tot;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) {
modify(ls[p], l, mid, x);
} else {
modify(rs[p], mid + 1, r, x);
}
}
bool query(int p, int l, int r, int x, int y) {
if (!p) return false;
if (x <= l && r <= y) return true;
int mid = (l + r) >> 1;
if (y <= mid) {
return query(ls[p], l, mid, x, y);
} else if (x > mid) {
return query(rs[p], mid + 1, r, x, y);
} else {
return query(ls[p], l, mid, x, mid) | query(rs[p], mid + 1, r, mid + 1, y);
}
}
};
SAM<N, 26> S;
SegmentTree<N << 1> T;
int main() {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++) {
S.insert(s[i] - 'a', i);
T.modify(rt[S.lst], 1, n, i);
}
for (int i = 1; i <= S.tot; i++) bin[S.len[i]]++;
for (int i = 1; i <= n; i++) bin[i] += bin[i - 1];
for (int i = 1; i <= S.tot; i++) t[bin[S.len[i]]--] = i;
for (int i = S.tot; i >= 1; i--) {
int u = S.lnk[t[i]], v = t[i];
rt[u] = T.merge(rt[u], rt[v]);
}
int ans = 1;
for (int i = 1; i <= S.tot; i++) {
int u = S.lnk[t[i]], v = t[i];
if (u == 0) {
f[v] = 1, top[v] = v;
continue;
}
int g = top[u];
if (T.query(rt[g], 1, n, S.pos[v] - S.len[v] + S.len[g], S.pos[v] - 1)) {
f[v] = f[u] + 1, top[v] = v;
} else {
f[v] = f[u], top[v] = top[u];
}
ans = std::max(ans, f[v]);
}
printf("%d\n", ans);
return 0;
}