九度题目1528：最长回文子串

题目1528：最长回文子串
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：781
解决：239
题目描述：
回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
回文子串，顾名思义，即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c...x,y,z组成的字符串，请输出其中最长的回文子串的长度。

输入：
输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于200000。

输出：
对于每组测试用例，输出一个整数，表示该组测试用例的字符串中所包含的的最长回文子串的长度。

样例输入：
abab
bbbb
abba

样例输出：
3
4
4

来源：
腾讯2013年实习生招聘二面面试题

有多种方法去求最长回文字串：

1.方法一：
中心求解法，从中间向两边检测，不断更新最长回文字符串大小，注意，可以分中心有一个字符的回文（奇数回文），如cabac，也有偶数的回文，如aabbaa，这要求我们要从中心或中心对称的两边字符往两边检测
AC代码：

#include<stdio.h>
#include<string.h>
char a[200010];
int FromeCenter(int l,int r,int n)//检测l至r之间的字符串中最长的回文字符串
{
     while(l>=0&&r<=n-1&&a[l]==a[r])
     {
        l--;r++;
     }
     return ((r-1)-(l+1)+1);
}
int main()
{
    int i,j,n,m,max,p1,p2;
    while(scanf("%s",a)!=EOF)
    {
       n=strlen(a);
       max=0;
       for(i=0;i<n;i++)
       {
          p1=FromeCenter(i,i,n);//以位置i为中心的最长回文字符串
          if(p1>max)
          max=p1;

          p2=FromeCenter(i,i+1,n);//以i和i+1之间的位置为中心的最长回文字符串
          if(p2>max)
          max=p2;
       }
       printf("%d\n",max);
       memset(a,0,sizeof(a));
    }
    return 0;
}

2.方法二，暴力求解法，只要从每个字符串开始向后检测，直至字符串的最后一个元素，检测每一个区间是否是回文字符串，更新最长的回文字符串长度；

代码(很不幸，因为长度为200000，所以华丽丽的超时了):

#include<stdio.h>
#include<string.h>
char a[200010];
int isPalinddrome(int l,int r,int n)
{
     while(l<r)
     {
        if(a[l]!=a[r])
        return 0;
        ++l;r--;
     }
     return 1;
}
int main()
{
    int i,j,n,m,max,p;
    while(scanf("%s",a)!=EOF)
    {
       n=strlen(a);
       max=0;
       for(i=0;i<n;i++)
       {
          for(j=i;j<n;j++)
          {
             if(isPalinddrome(i,j,n))
             {
                p=j-i+1;
                if(p>max)
                max=p;
             }
          }
       }
       printf("%d\n",max);
       memset(a,0,sizeof(a));
    }
    return 0;
}

3.方法三，动态规划法
如果aba是回文，那么cabac也是回文，于是我们得到一个递推的公式：
假设s[i,j]是回文字符串的话，定义p[i,j]=1;
于是p[i,j]=1是由(p[i+1,j-1]&&s[i]==s[j])递推出来的，如此往后，直到p[i,i+1]=1,此时满足s[i]=s[i+1],最后p[i,i]=1;

这个暂时，没有写出来.....