题目描述

使用字符串哈希的方式，时间复杂度为O(NlgN)

#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

typedef unsigned long long ULL;
const int N=2000010,base=131;
ULL hl[N],hr[N],p[N];

char str[N];

ULL get_hash(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}


int main(){
    int t=1;
    while(scanf("%s",str+1),strcmp(str+1,"END")){
        int n=strlen(str+1);
        //先将"#"插入原数组
        for(int i=2*n;i;i-=2){
            str[i]=str[i/2];
            str[i-1]='#';
        }
        n=2*n;
        p[0]=1;
        //字符串哈希过程
        for(int i=1,j=n;i<=n;i++,j--){
            hl[i]=hl[i-1]*base+str[i]-'a'+1;//正序
            hr[i]=hr[i-1]*base+str[j]-'a'+1;//逆序
            p[i]=p[i-1]*base;
        }

        //以每个点为中心，二分查找最大的相等的两端
        int ans=0;
        for(int i=1;i<=n;i++){
            int l=0,r=min(i-1,n-i);
            while(l<r){
                int mid=l+r+1>>1;
                if(get_hash(hl,i-mid,i-1)!=get_hash(hr,n+1-(i+mid),n+1-(i+1))) r=mid-1;
                else l=mid;
            }

            if(str[i-l]<='z'&&str[i-l]>='a') ans=max(ans,l+1);//如果查到的回文串的两端不是 # 的话，说明字符要多一个
            else ans=max(ans,l);
        }
        printf("Case %d: %d\n",t++,ans);

    }
    return 0;
}