题目
Given a string s,find the longest palindromic substring in S.You may assume that the maximum length of S is 1000,and there exist one unique longest palindromic substring.
分析与解法
如果一段字符串是回文,那么以某个字符为中心的前缀和后缀都是相同的.例如,一段回文串"aba",以b为中心,它的前缀与后缀都是相同的.
因此,我们可以枚举中心位置,然后在该位置上向左右两边扩展,记录并更新得到的回文长度.代码如下:
strng LongestPalidrome(string s){ int i,j,max,c; max=0; string ret; for(i=0;i<s.size();i++){ for(j=0;(i-j>=0) && (i+j<n);j++){ //假设只是奇数形式的字符串 if(s[i-j]!=s[i+j]) break; c=j*2+1; } if(c>max) { ret=s.substr(i-j+1,c); max=c; } for(j=0;(i-j>=0) && (i+j+1<n);j++){ //假设这是偶数形式的字符串 if(s[i-j]!=s[i+j+1]) break; c=j*2+2; } if(c>max) { ret=s.substr(i-j+1,c); max=c; } return ret; }
它们分别对于以i中心的，长度为奇数与偶数的两种情况.时间复杂度为O(n^2）.
在网上还有一种O(N)时间复杂度的算法,比较复杂.可以参考:http://blog.csdn.net/feliciafay/article/details/16984031
Longest Palindromic Substring -LeetCode
原文：http://www.cnblogs.com/sixue/p/3978082.html