题解 CF700E 【Cool Slogans】
xht
2020-03-15 02:44:37
> [CF700E Cool Slogans](https://codeforces.com/contest/700/problem/E)
## 题意
- 给定一个长度为 $n$ 的字符串 $s$。
- 你要构造一个最长的字符串序列 $t_{1\dots k}$，满足：
1. 对于 $i \in [1,k]$，$t_i$ 为 $s$ 的子串。
2. 对于 $i \in [2,k]$，$t_i$ 在 $t_{i-1}$ 中出现了至少两次。
- $n \le 2 \times 10^5$。
## 题解
对字符串建 SAM，用可持久化线段树合并求出每个节点的 $\operatorname{endpos}$ 集合。
在 $\operatorname{parent}$ 树上从根向下 dp，设 $f_i$ 表示到节点 $i$ 时的最大值。
如果一个父节点的子串在子节点的子串中出现了至少两次，则转移时 $f$ 加一，否则不变。
考虑如何判断是否出现了至少两次，设此时的子节点为 $x$，父节点为 $pa_x$。
找到 $x$ 对应的 $\operatorname{endpos}$ 中的任意一个位置 $pos$，则 $pos$ 处 $pa_x$ 的子串一定出现了一次。
那么另一次只要在 $[pos - \operatorname{len}(x) + \operatorname{len}(pa_x), pos - 1]$ 中有出现就行了。
总时间复杂度 $\mathcal O(n \log n)$。
## 代码
```cpp
const int N = 2e5 + 7;
struct T {
int l, r;
} t[N<<6|1];
int rt[N<<1], f[N<<1], g[N<<1], tot, ans = 1;
int insert(int l, int r, int x) {
int p = ++tot;
if (l == r) return p;
int mid = (l + r) >> 1;
if (x <= mid) t[p].l = insert(l, mid, x);
else t[p].r = insert(mid + 1, r, x);
return p;
}
int merge(int p, int q) {
if (!p || !q) return p | q;
int o = ++tot;
t[o].l = merge(t[p].l, t[q].l);
t[o].r = merge(t[p].r, t[q].r);
return o;
}
bool ask(int p, int l, int r, int L, int R) {
if (!p) return 0;
if (L <= l && R >= r) return 1;
int mid = (l + r) >> 1;
if (L <= mid && ask(t[p].l, l, mid, L, R)) return 1;
if (R > mid && ask(t[p].r, mid + 1, r, L, R)) return 1;
return 0;
}
struct SAM {
int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
char s[N];
int pos[N<<1];
inline void init() { pa[0] = -1; }
inline void add(int c, int o) {
int w = ++t, p = l;
len[w] = len[l] + 1, pos[w] = o;
while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
if (!~p) return pa[l=w] = 0, void();
int q = ch[p][c];
if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
int k = ++t;
pa[k] = pa[q], pos[k] = pos[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
len[k] = len[p] + 1, pa[w] = pa[q] = k;
while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
l = w;
}
inline void build() {
init();
for (int i = 1; i <= n; i++) add(s[i] - 'a', i);
}
int b[N<<1], c[N];
inline void sort() {
for (int i = 1; i <= t; i++) ++c[len[i]];
for (int i = 1; i <= n; i++) c[i] += c[i-1];
for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
}
inline void work() {
for (int i = 1, p = 0; i <= n; i++)
p = ch[p][s[i]-'a'], rt[p] = insert(1, n, i);
for (int i = t; i; i--)
rt[pa[b[i]]] = merge(rt[pa[b[i]]], rt[b[i]]);
for (int i = 1; i <= t; i++) {
int x = b[i];
if (!pa[x]) {
f[x] = 1, g[x] = x;
continue;
}
if (ask(rt[g[pa[x]]], 1, n, pos[x] - len[x] + len[g[pa[x]]], pos[x] - 1))
f[x] = f[pa[x]] + 1, g[x] = x;
else f[x] = f[pa[x]], g[x] = g[pa[x]];
ans = max(ans, f[x]);
}
}
} sam;
int main() {
rd(sam.n), rds(sam.s, sam.n), sam.build();
sam.sort(), sam.work(), print(ans);
return 0;
}
```