DDOSvoid's Blog

Luogu P3975 [TJOI2015]弦论

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

题目描述

https://www.luogu.com.cn/problem/P3975

简要题意：给定一个字符串 $S$ 和 $k$，求 $S$ 的本质不同/相同的第 $k$ 小子串

$|S|\le 5\times 10^5$

Solution

注意到子串为 $SAM$ 上的一条路径，而 $SAM$ 可以看成有向无环图

所以第 $k$ 小子串实际上就是第 $k$ 小路径，预处理一下直接做即可

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

int n, t, k;

char s[maxn];

struct SAM {
    int l, L, sz, nxt[26]; 
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
    rt = last = top = 1; 
    T[rt].L = T[rt].l = f[rt] = 0;
}

void extend(int ch) {
    int np = ++top, p = last; last = np;
    T[np].L = T[p].L + 1; T[np].sz = 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], suf[Maxn];
void rsort() {
    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) T[f[u]].sz += T[u].sz;
        else T[u].sz = 1;
    for (int i = top, u = tp[i]; i; u = tp[--i]) { 
        suf[u] = T[u].sz;
        for (int j = 0; j < 26; ++j)
            if (T[u].nxt[j]) suf[u] += suf[T[u].nxt[j]];
    }
}



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

    cin >> s + 1 >> t >> k; init_SAM(); n = strlen(s + 1); 
    for (int i = 1; i <= n; ++i) extend(s[i] - 'a');
    rsort(); if (k > suf[rt]) return cout << "-1\n", 0;
    int p = rt; 
    while (k) {
        for (int i = 0; i < 26; ++i)
            if (k <= suf[T[p].nxt[i]]) {
                p = T[p].nxt[i]; k -= T[p].sz; 
                cout << (char) ('a' + i);
                break; 
            }
            else k -= suf[T[p].nxt[i]]; 
    }
    return 0; 
}