POJ

给定一个字符串，求其最长回文子串的长度.

分析：马拉车算法模板题.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1000005;
int tot,maxr,mid,ans,T,f[N*2];
char ch,s[N*2];
int main(){
    while(1){
        tot=0;ans=0;maxr=0;mid=0;
        s[++tot]='~';s[++tot]='|';
        while(~scanf("%c",&ch)){
            if(ch>='a'&&ch<='z'){
                s[++tot]=ch;
                s[++tot]='|';
            }
            else if(ch=='E')return 0;
            else break;
        }
        for(int i=1;i<=tot;++i){
            if(i<maxr)f[i]=min(f[(mid<<1)-i],maxr-i);
            else f[i]=1;
            while(s[i-f[i]]==s[i+f[i]])f[i]++;
            if(f[i]+i>maxr)maxr=f[i]+i,mid=i;
            if(f[i]>ans)ans=f[i]; 
        }
        printf("Case %d: %d\n",++T,ans-1);
    }
    return 0;
}