ARC097 C : K-th Substring(300)
作成日：2018.09.24
最終更新日：2018.09.24
問題概要
文字列$s$の異なる部分文字列のうち、辞書順で$K$番目に小さいものを求めよ。
制約
$1 \leq |s| \leq 5000$
$1 \leq K \leq 5$
考え方
部分文字列は$O(|s|^2)$種類あるから、すべての部分文字列をソートするような方法では間に合わない。
そこで$K$が小さいことをうまく使えないかを考える。
$K=1$の時、答えは$s$に含まれる文字の中で辞書順最小であるものである。
$K=2$の時の答えは、それに$1$文字加えた文字列か$s$に含まれる文字の中で辞書順で$2$番目のものである。
同様に考えると、辞書順で$K$番目に小さい文字列は$K$文字以下になることが分かる。
すなわち調べる部分文字列は$O(NK)$個で良く、これらをソートすることにより答えを求めることができる。
ソースコード
マクロ等はこちら
int main(){
string s; cin >> s;
int K; cin >> K;
set<string> solve;
repp(i,0,s.size()) repp(j,1,6) solve.insert(s.substr(i,j));
auto ans = solve.begin();
repp(i,1,K) ++ans;
cout << *ans << endl;
return 0;
}解法まとめ
$5$($\geq K$)文字以下の部分文字列すべてを、重複をなくすためにsetに入れてソートする。
このようにした時の$K$番目の要素が答えとなる。(4-8行)