K-th Substring [AtCoder Regular Contest 097 C]

考察

1. どうみても300点問題に見えない
2. 制約に目立つものがある「K≦5」
3. 全ての連続部分列を列挙してソートした5番目というのは、文字列の長さが必ず5以下になっている。
4. ソートして最初の5つだけ分かっていればいいので、全ての連続部分列を列挙せずとも、文字列長が5以下のものだけ列挙すればいい

解法

https://beta.atcoder.jp/contests/arc097/submissions/2495089

全ての連続部分列ではなく、長さ5以下の連続部分列を列挙して、重複を除いてソートして、K番目を出力すると答え。
rep(i, 0, N) rep(j, 1, 6)で先頭のインデックスがiで長さjの連続部分列を取ってきて入れている。
重複を除くにはソートして、uniqueを使って除くことができる。
vectorよりもsetを使ったほうが楽かもしれない。

#define all(x) (x).begin(),(x).end()


string S;
int K, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> K;
    N = S.length();
 
    vector<string> s;
    rep(i, 0, N) rep(j, 1, 6) s.push_back(S.substr(i, j));
    sort(all(s));
    s.erase(unique(all(s)), s.end());
 
    cout << s[K - 1] << endl;
}