N lg N 最長回文子字串

用hash，枚舉端點，用二分搜。

放個最長回文的題目：http://acm.cs.nthu.edu.tw/problem/10378/

(話說在zerojudge 的 d978 好像要用 O(N) 耶！ )

#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long LL;
const int MAX_N = 1e6 + 6;
const int MAX_P = 31;
const LL mod = 1e9 + 7;

char s[MAX_N];
char c[MAX_N];
LL pow[MAX_N];
LL pre[MAX_N];
LL suf[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",s);
        c[0]=' ';
        c[1]='*';
        int len=2;
        for (int i=0;s[i] != '\0';i++) {
            c[len++] = s[i];
            if (s[i+1] != '\0') c[len++] = '*';
        }
        c[len++]='*';
        c[len+1]='\0';
        pow[0] = 1;
        len--;
        for (int i=1;len>=i;i++) {
            pow[i] = pow[i-1] * MAX_P;
            pow[i] %= mod;
            pre[i] = ( pre[i-1] + (c[i] * pow[i])%mod ) %mod;
        }
        suf[len+1] = 0;
        for (int i=len;i>=1;i--) {
            suf[i] = ( suf[i+1] + (c[i] * pow[len-i + 1])%mod) % mod;
        }
        //cout<<"c = "<<c<<endl;
        int ans=0;
        for (int i=2;len>i;i++) {
            //i is the middle point
            //cout<<"i-1 = "<<i-1<<" , len - i = "<<len - i<<" i = "<<i<<endl;
            int L=0,R=min(i-1,len-i)+1;  //L is okay
            if (R == 0) {
                continue;
            }
            while (R-L != 1) {
                int mid=(L+R)>>1;
                LL r = (pre[i+mid]-pre[i-1]+mod)%mod;
                LL l = (suf[i-mid]-suf[i+1]+mod)%mod;
                //cout<<"i = "<<i<<" , r = "<<r<<" , l = "<<l<<" , mid = "<<mid<<endl;
                if (len/2+1 == i) ;
                else if (i < len/2+1) r = r*pow[2*(len/2+1-i)]%mod;
                else if (i > len/2+1) l = l*pow[2*(i-len/2-1)]%mod;
                //cout<<"mid = "<<mid<<" , l = "<<l<<" , r = "<<r<<endl;
                if (l==r) L=mid;
                else R=mid;
            }
            //cout<<"i = "<<i<<" , L = "<<L<<endl;
            if (i%2==1) ans = max(ans,L);
            else ans = max(ans,L);
        }
        printf("%d\n",ans);
    }
}