# CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces

N, K ≤ 1e5
TL: 1000 ms
ML: 256 MB

O( | S | lg^2 | S | ) / O( | S | )

```#include <bits/stdc++.h>
using namespace std;

const int MAXLEN = ( int ) 1e5;
const int BASE = 311;
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };

string seq;
int pbase[ 2 ][ MAXLEN + 1 ], hpfx[ 2 ][ MAXLEN + 1 ];

int gh( int lb, int rb, int t ){
int res = ( 1LL * hpfx[ t ][ rb ] - 1LL * hpfx[ t ][ lb ] * pbase[ t ][ rb - lb ] ) % MOD[ t ];
if( res < 0 ) res += MOD[ t ];
return res;
}

struct hstring{
int lb, rb; // seq[ lb, rb )
hstring( int l, int r ) : lb( l ), rb( r ){}
friend bool operator < ( const hstring &a, const hstring &b ){
int al = a.lb, ar = a.rb, bl = b.lb, br = b.rb;
int sl = 0; // same length
for( int lo = 0, hi = min( ar - al, br - bl ); lo <= hi; ){
int mid = lo + hi >> 1;
int ng = 0;
ng |= gh( al, al + mid, 0 ) != gh( bl, bl + mid, 0 );
ng |= gh( al, al + mid, 1 ) != gh( bl, bl + mid, 1 );
if( not ng ){
sl = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if( ar - al == sl ) return false;
if( br - bl == sl ) return true;
return seq[ al + sl ] > seq[ bl + sl ];
}
};

signed main(){
ios::sync_with_stdio( 0 );
cin >> seq;
int K; cin >> K;
{ // preprocess power of bases and hash prefix sum
for( int t = 0; t < 2; ++t ){
pbase[ t ][ 0 ] = 1;
for( int i = 0; i < seq.size(); ++i ){
pbase[ t ][ i + 1 ] = 1LL * pbase[ t ][ i ] * BASE % MOD[ t ];
hpfx[ t ][ i + 1 ] = ( 1LL * hpfx[ t ][ i ] * BASE + seq[ i ] ) % MOD[ t ];
}
}
}
priority_queue< hstring > pq;
for( int i = 0; i < seq.size(); ++i ){
pq.emplace( i, i + 1 );
}
for( int i = 0; not pq.empty() and i + 1 < K; ++i ){
hstring hstr = pq.top(); pq.pop();
if( hstr.rb < seq.size() ){
++hstr.rb;
pq.emplace( hstr.lb, hstr.rb );
}
}
if( pq.empty() ){
cout << "No such line.\n";
} else{
cout << seq.substr( pq.top().lb, pq.top().rb - pq.top().lb ) << endl;
}
return 0;
}
```