Skip to content

S2OJ - 1024. 子串

题解615 字
# S2OJ # 数据结构 # Trie # 2018
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

你有一个长度为 nn 的 01 串 ss，你想知道它字典序第 kk 小的不同非空子串（即恰好存在 k−1k - 1 个子串比该子串字典序小，且它们（包括该子串本身）两两不同 ）。两个子串被认为不同当且仅当它们长度不同或者至少有一个位置上的字符不同。串 aa 的字典序小于串 bb 当且仅当 aa 为 bb 的一个前缀或者 aa 从左往右第一个与 bb 不同的字符比 bb 的小。

#输入格式

第一行两个正整数 n, kn,\ k。

第二行一个长度为 nn 的 01 串 ss，保证 ss 至少有 kk 种不同的子串。

#输出格式

输出一个 01 串，表示答案。

#样例输入

3 4
010

#样例输出

1

#数据规模与约定

  • 对于 20%20\% 的数据，n≤100n \le 100；
  • 对于 50%50\% 的数据，n≤1000n \le 1000；
  • 对于 70%70\% 的数据，n≤10000n \le 10000；
  • 对于 100%100\% 的数据，n≤105, k≤100n \le 10^5,\ k \le 100。

#思路

建一个 01 Trie ，并将 ss 的所有子串存进这个 Trie 树里面。

在查询时如果左子树（代表 00）包含的数值数量大于等于 kk ，那么就查询左子树内第 kk 小的子串；反之则查询右子树（代表 11）的第 k−sizeleftk - {size}_{left} 小的子串。

一直递归查询，直到查询到 ss 的第 kk 小字串时（即传入的 k=1k = 1 时）停止并退出程序，此时输出的内容即为答案。

#代码

C++
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
#include <bits/stdc++.h>

using namespace std;

int n, k, p, trie[10000005][2], size[10000005];
char s[100005];
bool a[100005];

void calcsize(int u) {
    if (trie[u][0]) calcsize(trie[u][0]);
    if (trie[u][1]) calcsize(trie[u][1]);
    size[u] += size[trie[u][0]] + size[trie[u][1]];
}

void print(int u, int k) {
    if (u != 1 && k-- == 1) {
        cout << endl;
        exit(0);
    }
    if (size[trie[u][0]] >= k) {
        cout << 0;
        print(trie[u][0], k);
    } else {
        cout << 1;
        print(trie[u][1], k - size[trie[u][0]]);
    }
}

int main() {
    cin >> n >> k >> s + 1;
    for (int i = 1; i <= n; i++) {
        a[i] = s[i] - '0';
    }
    p = 1;
    for (int i = 1; i <= n; i++) {
        int u = 1;
        for (int j = i; j <= min(n, i + k - 1); j++) {
            size[u = (trie[u][a[j]] ? trie[u][a[j]] : trie[u][a[j]] = ++p)] = 1;
        }
    }
    calcsize(1);
    print(1, k);
    return 0;
}