AtCoder ABC 097 C - K-th Substring (ARC 097 C) (緑色, 300 点)

本番出てなかったけどこれは...

ARC 097 C K-th Substring

問題概要

文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。

制約

• 1 <= |s| <= 5000
• 1 <= K <= 5

解法

K が小さいのが怪しい。 冷静に考えると、辞書順 K 番目の文字列の長さが K を超えることはない。したがって、s の連続する部分文字列のうち長さが K 以下のものだけを列挙してソートすればよい。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string S;
int K;

int main() {
  cin >> S >> K;
  vector<string> vec;
  for (int i = 0; i < S.size(); ++i) {
    for (int j = 1; j <= K; ++j) {
      string tmp = S.substr(i, j);
      vec.push_back(tmp);
    }
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  cout << vec[K-1] << endl;
}