CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces

題意：
給一個字串，你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。

資料規模：
N, K ≤ 1e5
TL: 1000 ms
ML: 256 MB

解法：
因為 K 很小，所以按字典序小的出隊，接上自己後一個字符再丟回一個優先隊列裡。瓶頸在字串比較的計算量，這裡用哈希解決，二分搜 LCP 後，比較 LCP 後那個字元即可。
據說暴力比這還快，但我既沒找出原因，也不知道是否可以構造讓暴力解法超時的數據

時間 / 空間複雜度：
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;
}