最长回文子串

题目：

求给定字符串的最长回文子串。

算法：

1.先进行预处理，字符串最初加上‘$’,'#',对于每个字符串前后加上#,是的字符串的长度为奇数，就不需要考虑奇数偶数的问题。'$','#'可自行定义。

# a # b # a # a # b #

2.求以每个树为中心的最长的回文串（包括#）。P[] : 1 2 1 4 1 2 5 2 1 2 1

P[i]-1 就是以Str[i]为中心的回文串在原串当中的长度。

#include<cstdio>  
#include<cstdlib>  
#include<iostream>  
#include<cstring>  
#include<cmath>  
#define L 2000000  
using namespace std;  
char s1[L],s2[L];  
int cnt[L],l1,l2;  
int main(){  
    int ans,t,i,j;  
    for(scanf("%d",&t);t--;){  
        scanf("%s",s1);  
        l1=strlen(s1);  
        l2=0;  
        s2[l2++]='$';  
        s2[l2++]='#';  
        for(i=0;i<l1;i++){  
            s2[l2++]=s1[i];  
            s2[l2++]='#';  
        }  
        s2[l2]='\0';  
        memset(cnt,0,sizeof cnt);  
        for(i=1,j=0;i<l2;i++){  
            if(cnt[j]+j>i)cnt[i]=min(cnt[2*j-i],cnt[j]-(i-j));  
            else cnt[i]=1;  
            for(cnt[i];s2[i-cnt[i]]==s2[i+cnt[i]];cnt[i]++) ;  
            if(i+cnt[i]>j+cnt[j])j=i;  
        }  
        ans=0;  
        for(i=0;i<l2;i++)  
            if(ans<cnt[i])ans=cnt[i];  
        printf("%d\n",ans-1);  
    }  
    return 0;  
}

解释：这里的cnt[j]是回文串的长度。

发现一个博客写的很好，引用一下，可以查看。http://blog.csdn.net/yzl_rex/article/details/7908259

最长回文子串

推荐阅读