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

1276 - 對稱之山 (Mountain) | TIOJ INFOR Online Judge
題意：
求最長回文子字串長度
題解：
同學縮隨便 dp 就可以過了 ??!!!
本來要寫 SA ( N lg N )，想想有 codebook 就寫 O( N ) 的 SA
拿出 codebook 後看到這個 完全不知道在幹麻就 AC惹

後注：
可以用哈希解決，理論上會過但TLE。
先塞無限大包住所有原本的數字，免去處理基偶回文問題。接著枚舉中央點，二分搜左右最長可以延伸到哪裡。

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