DDOSvoid's Blog

The 2021 ICPC Asia Shenyang Regional Contest M String Problem

发表于 更新于 分类于
本文字数： 4.5k 阅读时长 ≈ 4 分钟

题目描述

http://codeforces.com/gym/103427/problem/M

简要题意：给定一个串 $S$，对于它的每个前缀求这个前缀的字典序最大的子串

$|S|\le 10^6$

Solution

我们首先考虑一个暴力，我们按字典序从大到小枚举所有本质不同的子串，然后找到这个子串的最早出现位置，那么从这个位置向后一直延伸直到出现一个在之前被标记过的位置为止，这些位置的答案都是这个子串

注意到 $SAM$ 上的每一条路径都代表一个子串，那么我们直接在 $SAM$ 上按照字典序来 $dfs$ 即可，同时记录目前覆盖的位置，剪枝就是如果走到的位置已经大于等于已经覆盖的位置则可以直接退出，这样可以保证每个点只会经过最多一次

那么我们的复杂度就是构造 $SAM$ 的复杂度 $O(\sum L)$

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
#include <iostream>
#include <cstring>
#include <vector>
#define maxn 1000010
#define Maxn 2000010
using namespace std;

struct SAM {
    int L, pos, nxt[26];
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
    for (int i = 1; i <= top; ++i) {
        T[i].L = f[i] = 0; 
        fill(T[i].nxt, T[i].nxt + 26, 0); 
    }
    rt = last = top = 1; 
    T[rt].L = f[rt] = 0;
}

void extend(int ch) {
    int np = ++top, p = last; last = np;
    T[np].pos = T[np].L = T[p].L + 1; 
    while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
    if (!p) return f[np] = rt, void();
    int q = T[p].nxt[ch];
    if (T[q].L - 1 == T[p].L) f[np] = q;
    else {
        int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
        for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[np] = f[q] = nq;
    } 
}

int tax[maxn], tp[Maxn]; 
void rsort(int n) {
    for (int i = 1; i <= n; ++i) tax[i] = 0; 
    for (int i = 1; i <= top; ++i) ++tax[T[i].L];
    for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
    for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
    for (int i = top, u = tp[i]; i; u = tp[--i]) {
        if (!T[f[u]].pos) T[f[u]].pos = T[u].pos;
        else T[f[u]].pos = min(T[f[u]].pos, T[u].pos);
    }
}

int ans[maxn], k;
void dfs(int u, int len) {
    for (int ch = 25; ~ch; --ch) {
        int v = T[u].nxt[ch]; if (!v || T[v].pos >= k) continue;
        dfs(v, len + 1); 
    }
    if (u != rt) ans[T[u].pos] = len, k = T[u].pos;
}

int n;
char s[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); init_SAM();
    for (int i = 1; i <= n; ++i) extend(s[i] - 'a'); rsort(n);
    k = n + 1; dfs(rt, 0);
    for (int i = 1, mn = top + 1, k; i <= n; ++i) {
        if (ans[i]) mn = ans[i];
        cout << i - mn + 1 << " " << i << "\n";
    }
    return 0;
}

另外还有一个后缀树的做法，对于后缀树上一个节点，注意到这个节点对应的答案是一个区间，那么我们考虑按字典序进行 $dfs$ 后，从字典序大的节点开始赋值，每次相当于合并一个区间，后面的合并不能影响前面的操作，那么可以使用并查集来操作，另外后缀树上每个节点的出现位置我们只需要记第一个即可，因为每个节点所代表的串只有可能在第一个位置成为答案

时间复杂度 $O(L(\sum + \alpha))$

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
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <tuple>
#define maxn 1000010
#define Maxn 2000010
#define ll long long
using namespace std;

int n;
char s[maxn];

vector<pair<int, int>> G[Maxn];

struct SAM {
    int pos, L, l, nxt[26]; 
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
    for (int i = 1; i <= top; ++i) {
        T[i].pos = T[i].L = T[i].l = f[i] = 0; 
        fill(T[i].nxt, T[i].nxt + 26, 0); 
    }
    rt = last = top = 1; 
    T[rt].pos = T[rt].L = T[rt].l = f[rt] = 0;
}

void extend(int ch) {
    int np = ++top, p = last; last = np;
    T[np].pos = T[np].L = T[p].L + 1; 
    while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
    if (!p) return f[np] = rt, void();
    int q = T[p].nxt[ch];
    if (T[q].L - 1 == T[p].L) f[np] = q;
    else {
        int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
        for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[np] = f[q] = nq;
    } 
}

int tax[maxn], tp[Maxn]; 
void rsort(int n) {
    for (int i = 1; i <= n; ++i) tax[i] = 0; 
    for (int i = 1; i <= top; ++i) ++tax[T[i].L];
    for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
    for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
    for (int i = top, u = tp[i]; i > 1; u = tp[--i]) {
        T[f[u]].pos = max(T[f[u]].pos, T[u].pos);
        T[u].l = T[f[u]].L + 1;
        G[f[u]].emplace_back(s[T[u].pos - T[u].l + 1] - 'a', u);
    }
}

int fa[maxn], ans[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void merge(int x, int y, int z) {
    x = find(x); 
    while (x <= y) {
        ans[x] = z; 
        x = fa[x] = find(x + 1); 
    }
}

vector<tuple<int, int, int>> A;
void dfs(int u) {
    sort(G[u].begin(), G[u].end());
    if (u != rt)
        A.emplace_back(n - (T[u].pos - T[u].l + 1) + 1, n - (T[u].pos - T[u].L + 1) + 1, n - T[u].pos + 1);
    for (auto [w, v] : G[u]) dfs(v); 
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); reverse(s + 1, s + n + 1); init_SAM();
    for (int i = 1; i <= n; ++i) extend(s[i] - 'a'); 
    rsort(n); init_fa(n + 1); dfs(rt); reverse(A.begin(), A.end());
    for (auto [l, r, v] : A) merge(l, r, v);
    for (int i = 1; i <= n; ++i) cout << ans[i] << " " << i << "\n";
    return 0;
}