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