POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal

題意：
給一個字串，問最多和最少可以拆分成幾個偶數長度迴文，存在的話輸出方案。

資料規模：
The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. The word is written in one line with no spaces between letters.

解法：
對原字串做正反各一次 hash 之後可以支持 lg | S | 時間查詢任一子字串是否為迴文。
dp_max[ i ] : 前 i 個字符最多可以拆分的偶數迴文數
dp_max[ i ] = max( dp_max[ j ] + 1, if S[ j, i ) is palindrome }

時間 / 空間複雜度：
O( | S | lg | S | ) / O( | S | )

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

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x <= v ) return 0;
  x = v; return 1;
}

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
  if( x >= v ) return 0;
  x = v; return 1;
}

const int MAXN = 200;
const int MOD = ( int ) 1e9 + 7;
const int BASE = 311;

string seq;

int pbase[ MAXN + 1 ];
int hpfx[ MAXN + 1 ];
int rhpfx[ MAXN + 1 ];

int dp_max[ MAXN + 1 ];
int pre_max[ MAXN + 1 ];
int dp_min[ MAXN + 1 ];
int pre_min[ MAXN + 1 ];

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

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> seq;
  {
    pbase[ 0 ] = 1;
    for( int i = 0; i < seq.size(); ++i ){
      pbase[ i + 1 ] = 1LL * pbase[ i ] * BASE % MOD;
      hpfx[ i + 1 ] = ( 1LL * hpfx[ i ] * BASE + seq[ i ] ) % MOD;
      rhpfx[ i + 1 ] = ( 1LL * rhpfx[ i ] * BASE + seq[ seq.size() - 1 - i ] ) % MOD;
    }
  }
  {
    for( int i = 1; i <= seq.size(); ++i ){
      dp_max[ i ] = - 0x3f3f3f3f;
      dp_min[ i ] = 0x3f3f3f3f;
    }
    for( int i = 0; i < seq.size(); ++i ){
      for( int j = i + 2; j <= seq.size(); j += 2 ){
        if( gh( hpfx, i, j ) == gh( rhpfx, seq.size() - j, seq.size() - i ) ){
          if( upmax( dp_max[ j ], dp_max[ i ] + 1 ) ){
            pre_max[ j ] = i;
          }
          if( upmin( dp_min[ j ], dp_min[ i ] + 1 ) ){
            pre_min[ j ] = i;
          }
        }
      }
    }
  }
  {
    if( dp_min[ seq.size() ] == 0x3f3f3f3f ){
      cout << "NIE\n";
      exit( 0 );
    }
  }
  vector< int > mini, maxi;
  {
    for( int i = seq.size(); i; i = pre_min[ i ] ){
      mini.push_back( i );
    }
    mini.push_back( 0 );
    for( int i = seq.size(); i; i = pre_max[ i ] ){
      maxi.push_back( i );
    }
    maxi.push_back( 0 );
  }
  {
    for( int i = mini.size() - 1; i > 0; --i ){
      cout << seq.substr( mini[ i ], mini[ i - 1 ] - mini[ i ] ) << " \n"[ i - 1 == 0 ];
    }
    for( int i = maxi.size() - 1; i > 0; --i ){
      cout << seq.substr( maxi[ i ], maxi[ i - 1 ] - maxi[ i ] ) << " \n"[ i - 1 == 0 ];
    }
  }
  return 0;
}