# TIOJ 1276 . 對稱之山 (Mountain) ( Z-value Palindrome )

1276 - 對稱之山 (Mountain) | TIOJ INFOR Online Judge

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

typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef pair< int, int > pii;
typedef vector< pii > vp;

const int MAXL = 1e7 + 2;

int len, sel;
int s[ MAXL * 2 ], se[ MAXL * 2 ];
int pal[ MAXL * 2 ];

int g[ MAXL ];

const int INF = 0x3f3f3f3f;

void genpal(){
int i, j, r, t;
sel = 2 * len + 1;
for(i=0;i<sel;i++) se[i]=(i&1)?s[i>>1]:INF; pal[0]=0;
j=r=0;
for(i=1;i<sel;i++) {
t=min(r>=i?pal[2*j-i]:0,r-i+1);
for(;i-t>=0&&i+t<sel;t++) if(se[i-t]!=se[i+t]) break; pal[i]=--t;
if(i+t>r) { r=i+t; j=i; }
}
}

void init(){
scanf( "%d", &len );
for( int i = 0; i < len; ++i )
scanf( "%d", s + i );
genpal();
int maxv = 0;
for( int i = 1; i < sel; ++i )
maxv = max( maxv, pal[ i ] );
printf( "%d\n", maxv - 1 );
}

void solve(){

}

signed main(){
ios::sync_with_stdio( false );
init();
solve();
return 0;
}
```
```// hash
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;

const int INF = 0x3f3f3f3f;

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

const int bsz = 2; // number of hashes = base size
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };
const int BASE[] = { ( int ) 3e5 + 1, ( int ) 3e5 + 7 };

int N;
vi A;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ];
}

int get_hash( const vvi &phash, const vvi &fbase, int ver, int ql, int qr ){ // [ ql, qr )
int f = fbase[ ver ][ qr - ql ];
int res = phash[ ver ][ qr ] - 1LL * phash[ ver ][ ql ] * f % MOD[ ver ];
res %= MOD[ ver ], res += MOD[ ver ], res %= MOD[ ver ];
return res;
}

void solve(){ // finds longest palindrome
vi s( 2 * N + 1 );
for( int i = 0; i < 2 * N + 1; ++i )
s[ i ] = ( ~i & 1 ) ? INF : A[ i >> 1 ];
vi rs = s; reverse( rs.begin(), rs.end() );

vvi fbase( bsz, vi( s.size() + 1 ) );
vvi shash( bsz, vi( s.size() + 1 ) );
vvi rshash( bsz, vi( s.size() + 1 ) );
for( int i = 0; i < bsz; ++i ){
fbase[ i ][ 0 ] = 1;
for( int j = 0; j + 1 <= s.size(); ++j )
fbase[ i ][ j + 1 ] = 1LL * fbase[ i ][ j ] * BASE[ i ] % MOD[ i ],
shash[ i ][ j + 1 ] = ( 1LL * shash[ i ][ j ] * BASE[ i ] + s[ j ] ) % MOD[ i ],
rshash[ i ][ j + 1 ] = ( 1LL * rshash[ i ][ j ] * BASE[ i ] + s[ s.size() - j - 1 ] ) % MOD[ i ];
} // shash[ 0 ] = s[ 0 ], shash[ 1 ] = s[ 0 ] * BASE + s[ 1 ], ...

int ans = -1;
for( int i = 1; i + 1 < s.size(); ++i ){
int lb = 0, rb = min( i, ( int ) s.size() - i - 1 );
while( lb <= rb ){
int mid = lb + rb >> 1;

int ok = 1;
for( int t = 0; t < bsz; ++t ){
int ri = s.size() - i - 1;
if( get_hash( shash, fbase, t, i - mid, i )
!= get_hash( rshash, fbase, t, ri - mid, ri ) ){
ok = 0;
break;
}
}

if( ok )
ans = max( ans, mid * 2 + 1 ),
lb = mid + 1;
else
rb = mid - 1;
}
}
cout << ans / 2 - 1 << endl;
}

signed main(){
ios::sync_with_stdio( 0 );
cin.tie( 0 ), cout.tie( 0 );
init();
solve();
return 0;
}
```