一、nlogn求最长回文串
POJ3974

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
#define llu unsigned long long
using namespace std;
const int maxn=1000010;
char str[maxn];
llu h1[maxn],h2[maxn],p[maxn];
inline llu H1(int i,int j)
{
    return h1[j]-h1[i-1]*p[j-i+1];
}

inline llu H2(int i,int j)
{
    return h2[i]-h2[j+1]*p[j-i+1];
}
int main(void)
{
    int pp=0;
    p[0]=1;
    for(int i=1;i<maxn;i++)
        p[i]=p[i-1]*131;

    while(scanf("%s",str+1)!=EOF)
    {
        int ans=0;
        int len=strlen(str+1);
        if(len==3&&str[1]=='E'&&str[2]=='N'&&str[3]=='D') break;

        h1[0]=0;
        h2[len+1]=0;
        for(int i=1;i<=len;i++) h1[i]=h1[i-1]*131+str[i]-'a'+1;
        for(int i=len;i>=1;i--) h2[i]=h2[i+1]*131+str[i]-'a'+1;

        int l,r,mid;
        for(int pos=1;pos<=len;pos++)
        {
            l=0,r=min(pos-1,len-pos+1);
            while(l<r)
            {
                mid=(l+r+1)/2;
                if(H1(pos-mid,pos-1)==H2(pos,pos+mid-1)) l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2);


            l=0,r=min(pos-1,len-pos);
            while(l<r)
            {
                mid=(l+r+1)/2;
                if(H1(pos-mid,pos)==H2(pos,pos+mid)) l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2+1);

        }
        printf("Case %d: %d\n",++pp,ans);
    }
    return 0;
}