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; }