CFR 126 B. Password ( Hash + Binary Search )

Problem - 126B - Codeforces
題意：
給一個字串，求最長子字串，滿足存在一個前綴和它相等，一個後綴和它相等，一個非前綴也非後綴也和它相等。
解法：
先預處理字串的 rolling hash，接著把滿足所有前綴和後綴相等的長度押入一個有序容器。
接著對那個容器裡的長度做二分搜，每次花費O( N )確定這個長度的子字串是否有一個非前綴也非後綴和該長度的前綴相等。

const int MSZ = 2; // MOD size ( number of attempts of verifying hash
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };
const int BASE[] = { ( int ) 1023, ( int ) 1e4 + 7 };

string seq;

void init(){
    cin >> seq;
}

vvi pbase; // power base
vvi phash; // prefix hash

void preprocess(){
    pbase = phash = vvi( MSZ, vi( seq.size() + 1 ) );
    for( int i = 0; i < MSZ; ++i ){
        pbase[ i ][ 0 ] = 1;
        for( int j = 0; j < seq.size(); ++j ){
            pbase[ i ][ j + 1 ] = 1LL * pbase[ i ][ j ] * BASE[ i ] % MOD[ i ],
            phash[ i ][ j + 1 ] = ( 1LL * phash[ i ][ j ] * BASE[ i ] + seq[ j ] ) % MOD[ i ];
        }
    }
}

int get_hash( const vi &pbase, const vi &phash, int mod, int ql, int qr ){ // [ ql, qr )
    int res = phash[ qr ] - 1LL * phash[ ql ] * pbase[ qr - ql ] % mod;
    res %= mod, res += mod, res %= mod;
    return res;
}

void solve(){
    vi test;
    for( int i = 1; i < seq.size(); ++i ){
        int ok = 1;
        for( int j = 0; j < MSZ; ++j )
            if( get_hash( pbase[ j ], phash[ j ], MOD[ j ], 0, i ) != get_hash( pbase[ j ], phash[ j ], MOD[ j ], seq.size() - i, seq.size() ) )
                ok = 0;
        if( ok )
            test.push_back( i );
    }

    int lb = 0, rb = test.size() - 1;
    int ans = -1;
    while( lb <= rb ){
        int mid = lb + rb >> 1;
        int x = test[ mid ];

        int ok = 0;

        for( int j = 1; j < seq.size() - x; ++j ){
            int ng = 0;
            for( int k = 0; k < MSZ; ++k )
                if( get_hash( pbase[ k ], phash[ k ], MOD[ k ], 0, x ) != get_hash( pbase[ k ], phash[ k ], MOD[ k ], j, j + x ) )
                    ng = 1;
            if( not ng )
                ok = 1;
        }

        if( ok )
            ans = mid, lb = mid + 1;
        else
            rb = mid - 1;
    }
    if( ans == -1 )
        cout << "Just a legend" << endl;
    else
        cout << seq.substr( 0, test[ ans ] ) << endl;
}