IOICJ 88 Necklace 2 ( Hash )

Problem Description:
lo has a string Slo, and li has a string Sli. You want to find the maximum length of common palindrome substring of both strings.

Constraints:
1≤T≤30
1≤|Slo|,|Sli|≤100000

Sample Input:
2
abaxyza
xyzaaba
abaxyzwvcddcpirikapirirarapoporinapeperudo
vwzyxcddcaba

Sample Output:
3
4

Solution:
Insert letter '$' between every symbol ( and also both ends ) of both original strings. Then preprocess the maximum length that could be reached away from every position i, such that that extended substring is a palindrome, and denote it as max_pal[ i ]. The preprocessing could be done with either Manacher's Algorithm, or simply hashing on both left to right and right to left and applying binary search. Then binary search for the answer, during the search, first enumerate all hashes of palindrome substrings with the applicable length of the first string, emplace them in a BST structure, then enumerate all hashes of substrings with the applicable length of the second string and see whether some element in the BST matches.

Note:
I didn't realize that :
24: ns += s.substr( i, 1 ) + "$";
where ns = ns + ... is O( N ^ 2 ) and spent unnecessary time on debugging until some one told me.

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

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< string > vs;

const int INF = 0x3f3f3f3f;
const int MOD9 = ( int ) 1e9 + 9;
const int BASE = 311;

string A, B;

void init(){
  cin >> A >> B;
  if( not ( A.size() >= B.size() ) ){
    swap( A, B );
  }
}

void convert_s( string &s ){
  string ns = "$";
  for( int i = 0; i < s.size(); ++i )
    ns += s.substr( i, 1 ) + "$";
  swap( s, ns );
}

vi pbase;
vi apfxh, rvapfxh;
vi bpfxh, rvbpfxh;
vi amax_pal; // i を中心とする A の部分文字列の中、右に伸びれる最大の長さ
vi bmax_pal;

int get_h( const vi &pfxh, int lb, int rb ){ // [ lb, rb )
  int res = pfxh[ rb ] - 1LL * pfxh[ lb ] * pbase[ rb - lb ] % MOD9;
  if( res < 0 ) res += MOD9;
  return res;
}

void build_max_pal( const vi &pfxh, const vi &rvpfxh, vi &maxp ){
  maxp = vi( pfxh.size() );
  for( int i = 0; i + 1 < pfxh.size(); ++i ){
    int maxd = min( i, ( int ) pfxh.size() - 1 - ( i + 1 ) );
    for( int lb = 0, rb = maxd; lb <= rb; ){
      int mid = lb + rb >> 1;
      int lhv = get_h( pfxh, i - mid, i );
      int rlen = pfxh.size() - 1 - ( i + 1 );
      int rhv = get_h( rvpfxh, rlen - mid, rlen );
      if( lhv == rhv ){
        maxp[ i ] = mid;
        lb = mid + 1;
      } else{
        rb = mid - 1;
      }
    }
  }
}

void preprocess(){
  convert_s( A );
  convert_s( B );
  apfxh = rvapfxh = pbase = vi( A.size() + 1 );
  pbase[ 0 ] = 1;
  for( int i = 0; i < A.size(); ++i ){
    pbase[ i + 1 ] = 1LL * pbase[ i ] * BASE % MOD9;
    apfxh[ i + 1 ] = ( 1LL * apfxh[ i ] * BASE + A[ i ] ) % MOD9;
    rvapfxh[ i + 1 ] = ( 1LL * rvapfxh[ i ] * BASE + A[ A.size() - 1 - i ] ) % MOD9;
  }
  rvbpfxh = bpfxh = vi( B.size() + 1 );
  for( int i = 0; i < B.size(); ++i ){
    bpfxh[ i + 1 ] = ( 1LL * bpfxh[ i ] * BASE + B[ i ] ) % MOD9;
    rvbpfxh[ i + 1 ] = ( 1LL * rvbpfxh[ i ] * BASE + B[ B.size() - 1 - i ] ) % MOD9;
  }
  build_max_pal( apfxh, rvapfxh, amax_pal );
  build_max_pal( bpfxh, rvbpfxh, bmax_pal );
}

void solve(){
  int ans = 0;
  for( int lb = 1, rb = B.size(); lb <= rb; ){
    int mid = lb + rb >> 1;
    set< int > bag;
    for( int i = mid; i + mid + 1 <= A.size(); ++i ){
      if( amax_pal[ i ] < mid ) continue;
      bag.emplace( get_h( apfxh, i - mid, i + mid + 1 ) ); // [ lb, rb )
    }
    int ok = 0;
    for( int i = mid; i + mid + 1 <= B.size(); ++i ){
      int bh = get_h( bpfxh, i - mid, i + mid + 1 );
      if( bmax_pal[ i ] < mid ) continue;
      if( not bag.count( bh ) ) continue;
      ok = 1;
      break;
    }
    if( ok ){
      ans = 2 * mid + 1;
      lb = mid + 1;
    } else{
      rb = mid - 1;
    }
  }
  cout << ans / 2 << endl;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int T; cin >> T;
  while( T-- ){
    init();
    preprocess();
    solve();
  }
  return 0;
}