C - K-th Substring | AtCoder Regular Contest 097

priority queueに(s[i,i], i), 1<=i<=Nを挿入していく。あとは先頭の要素をとってきて右端を1個伸ばしたものをpriority queueに挿入していく。ダイクストラ法で辺によって隣接する頂点を追加するのに似ている。s[l, r] <= s[l, r+1]なのでs[l, r]が取り出されたのよりも後にs[l, r+1]が取り出されるので正しい。異なる部分文字列をK個調べたら終了。

string S;
cin >> S;
int K;
cin >> K;
const int N = sz(S);
using P = pair<string, int>;
priority_queue<P,vector<P>,greater<P> > T;
rep(i, N) {
    string s;
    s += S[i];
    T.push(mp(s, i));
}

string re = "";
rep(i, K) {
    auto p = T.top(); T.pop();
    int j = p.second + sz(p.first);
    if (re == p.first) {
        --i;
    }
    re = p.first;
    if (j < N) {
        p.first += S[j];
        T.push(p);
    }
}
cout << re << endl;