最长的回文串——hdu3068

http://acm.hdu.edu.cn/showproblem.php?pid=3068

abcba 5

aab 2

在一个字符串里寻找一条最长的回文串

比较直接的想法是枚举中心点 然后像两边扩散，但这样不仅要考虑最长子串的奇数偶数情况，而且时间复杂度会很高，因为会有比较多的重复计算

分析 aaaab, abcba

变成 #a#a#a#a#b# ,    #a#b#c#b#a#

就都成了奇数子串

现在再用一个数组P保存到该点的最长回文

#a#a#a#a#b#

12345432131

if( mx > i )
p[i] = min( p[2*id-i], mx-i );

这一句减少了重复计算过程

至于为什么要取小，考虑

abcbabc

#include<stdio.h>

#include<string.h>

char ss[];

char ne[];

int p[];

int len;

int min(int a,int b){

    return a>b?b:a;

}

void pre()

{

    int i,n2;

    len=strlen(ss);

    n2=len*;

    for(i=;i<=n2;i++){

        p[i]=;

    }

    ne[]='#';

    for(i=;i<len;i++){

        ne[*i+]=ss[i];

        ne[*i+]='#';

    }

    ne[*len+]='@';//end

}

int cal(){

    int i,max=;

    int id;

    int n=len*;

    int mx = ;

    for(i=; i<n; i++)

    {

        if( mx > i )

            p[i] = min( p[*id-i], mx-i );

        else

            p[i] = ;

        for(; ne[i+p[i]] == ne[i-p[i]]; p[i]++)

            ;

        if( p[i] + i > mx )

        {

            mx = p[i] + i;

            id = i;

        }

    }

    for(i=;i<n;i++){

        if(p[i]>max)max=p[i];

    }

    return max;

}

int main()

{

    int n2,i,max=,p;

    while(scanf("%s",ss)!=EOF){

        pre();max=cal();

        printf("%d\n",max-);

    }

    return ;

}