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;
}