840
九度题目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;
这个暂时，没有写出来.....
最后更新：2017-04-03 12:56:25