最长回文子串（百度笔试题和hdu 3068）

本文主要是介绍最长回文子串（百度笔试题和hdu 3068），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

版权所有。所有权利保留。

欢迎转载，转载时请注明出处：

http://blog.csdn.net/xiaofei_it/article/details/17123559

求一个字符串的最长回文子串。注意子串是连续的，子序列是不连续的。对于最长回文子序列，要用动态规划解，具体请看：

http://blog.csdn.net/xiaofei_it/article/details/16813591

本题是百度笔试题，但和hdu 3068类似。所以直接给出hdu 3068的代码。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 230000
#define min(a,b) ((a)<(b)?(a):(b))
char s[MAX],str[MAX];
int i,len,id,mx,p[MAX];
int main()
{while (scanf("%s",str)!=EOF){s[0]='#';len=strlen(str);for (i=0;i<len;i++){s[i*2+1]=str[i];s[i*2+2]='#';}len=len*2+1;p[0]=1;mx=0;id=0;for (i=1;i<len;i++){if (mx>=i){if (2*id-i>=0)p[i]=min(p[2*id-i],mx-i+1);elsep[i]=mx-i;}else{p[i]=1;}for (;i+p[i]<len&&i-p[i]>=0&&s[i+p[i]]==s[i-p[i]];p[i]++);if (p[i]+i-1>mx){mx=p[i]+i-1;id=i;}}mx=0;for (i=0;i<len;i++)if (mx<p[i]-1)mx=p[i]-1;cout<<mx<<endl;}return 0;
}

这篇关于最长回文子串（百度笔试题和hdu 3068）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---