一、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;
}