CFR 129 D. String ( Priority Queue )

Problem - D - Codeforces
因為關鍵的只有最小的10萬個，所以可以用priority queue模擬。不過現在這個方法過不了，因為judge time 變成兩倍。抓了別人的code來測試果真如此。雖然說有另一種解法是用後綴陣列，我這禮拜要趕緊學起來。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 1e5 + 5;

string s;
int k;

typedef pair< string, int > psi;

void solve(){
    if( (long long)s.size() * ( s.size() + 1 ) / 2 < k ){
        cout << "No such line." << "\n";
        return;
    }
    priority_queue< psi, vector< psi >, greater< psi > > pq;
    for( int i = 0; i < s.size(); ++i )
        pq.push( psi( s.substr( i, 1 ), i ) );
    while( --k ){
        string z = pq.top().first;
        int idx = pq.top().second;
        pq.pop();
        if( idx + 1 < s.size() ) pq.push( psi( z + s[ idx + 1 ], idx + 1 ) );
    }
    cout << pq.top().first << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    cin >> s;
    cin >> k;
    solve();
    return 0;
}