Skip to content

S2OJ - 1024. 子串

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

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

输入格式

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

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

输出格式

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

样例输入

3 4
010

样例输出

1

数据规模与约定

  • 对于 20%20\% 的数据,n100n \le 100
  • 对于 50%50\% 的数据,n1000n \le 1000
  • 对于 70%70\% 的数据,n10000n \le 10000
  • 对于 100%100\% 的数据,n105, k100n \le 10^5,\ k \le 100

思路

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

在查询时如果左子树(代表 00)包含的数值数量大于等于 kk ,那么就查询左子树内第 kk 小的子串;反之则查询右子树(代表 11)的第 ksizeleftk - {size}_{left} 小的子串。

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

代码

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