Problem

我们定义一个字符串$a$比一个字符串$b$酷

当$b$在$a$中作为子串出现至少两次

现在给定一个字符串$S$,要求找到最长的子串序列$S_1$,$S_2$,$S_3$……

要求对于任意$i$,$S_{i+1}$比$S_i$酷

Solution

我们发现,如果我们要找一个字符串$b$,使得字符串$a$作为子串在其中出现至少两次

即$a$的$endpos$集合在$[pos[b]-len[b]+len[a],pos[b]]$中出现至少两次

最短的$b$串一定是以$a$为前缀且以$a$为后缀的,可以得出结论$a$为$b$的$border$

那么只要$a$的$endpos$集合在$[pos[b]-len[b]+len[a],pos[b]-1]$中出现即可

用线段树维护$endpos$,将$endpos$按$fail$链进行线段树合并得到每个节点的$endpos$集合,在对应集合查询区间$[pos[b]-len[b]+len[a],pos[b]-1]$是否有值即可

我们需要在$fail$链节点上保存最长子序列的最后一位,每次扩展时在这一位的线段树上查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
const int N = 400000 + 10;
int Tr(char c) { return c - 'a'; }
int p, q, np, nq, cnt, lst, a[N][26], l[N], f[N], pos[N];
void extend(int c, int ps) {
p = lst;
np = lst = ++cnt;
l[np] = l[p] + 1;
pos[np] = ps;
while (!a[p][c] && p) a[p][c] = np, p = f[p];
if (!p)
f[np] = 1;
else {
q = a[p][c];
if (l[p] + 1 == l[q])
f[np] = q;
else {
nq = ++cnt;
l[nq] = l[p] + 1;
pos[nq] = pos[q];
memcpy(a[nq], a[q], sizeof(a[q]));
f[nq] = f[q];
f[np] = f[q] = nq;
while (a[p][c] == q) a[p][c] = nq, p = f[p];
}
}
}
int ls[N * 30], rs[N * 30], rt[N], tot;
void upd(int &x, int l, int r, int p) {
x = ++tot;
if (l == r) return;
int mid = l + r >> 1;
p <= mid ? upd(ls[x], l, mid, p) : upd(rs[x], mid + 1, r, p);
}
int merge(int x, int y) {
if (!x || !y) return x + y;
int z = ++tot;
ls[z] = merge(ls[x], ls[y]);
rs[z] = merge(rs[x], rs[y]);
return z;
}
int qry(int x, int l, int r, int ql, int qr) {
if (!x) return 0;
if (ql <= l && qr >= r) return 1;
int mid = l + r >> 1, res = 0;
if (ql <= mid) res |= qry(ls[x], l, mid, ql, qr);
if (qr > mid) res |= qry(rs[x], mid + 1, r, ql, qr);
return res;
}
char s[N];
int n, b[N], x[N], r[N], top[N], dp[N];
void solve() {
int ans = 1;
cnt = 0, lst = ++cnt;
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
extend(Tr(s[i]), i);
upd(rt[lst], 1, n, i);
}
for (int i = 1; i <= cnt; i++) b[l[i]]++;
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
for (int i = 1; i <= cnt; i++) x[b[l[i]]--] = i;
for (int i = cnt; i > 1; i--) rt[f[x[i]]] = merge(rt[f[x[i]]], rt[x[i]]);
for (int i = 2; i <= cnt; i++) {
int u = x[i], fu = f[u];
if (fu == 1) {
dp[u] = 1, top[u] = u;
continue;
}
int t = qry(rt[top[fu]], 1, n, pos[u] - l[u] + l[top[fu]], pos[u] - 1);
dp[u] = dp[fu] + t;
top[u] = t ? u : top[fu];
ans = max(ans, dp[u]);
}
printf("%d\n", ans);
}
int main() {
solve();
return 0;
}