LintCode 最长回文子串

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

给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。

样例
给出字符串 “abcdzdcab”，它的最长回文子串为 “cdzdc”。

挑战
O(n2) 时间复杂度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。

第一次AC的连O（n2）都不是的，是O（n3），遍历所有子串。代码如下：

class Solution:"""@param: s: input string@return: the longest palindromic substring"""def longestPalindrome(self, s):# write your code heren=len(s)result=""m=0for i in range(n):for j in range(n-1,i,-1):if s[j]==s[i]:temp=s[i:j+1]res=self.judge(temp)if res>m:result=tempm=resif m<1:result=s[i]return resultdef judge(self,s):n=len(s)if n==0:return for i in range(n/2):if s[i]!=s[n-1-i]:return -1return n

然后参考了曾会玩的文章，感谢。
O（n2）的算法。利用回文串的对称性，从中心向两端扩展。对整个字符串来说，可能为中心的包括n个字符，和n-1个间隙，分两种情况来判断。代码如下：

class Solution:"""@param: s: input string@return: the longest palindromic substring"""def longestPalindrome(self, s):# write your code heren=len(s)result=""m=0for i in range(n):j=1temp=s[i]while(i-j>=0 and i+j<n ):if s[i-j]==s[i+j]:temp=s[i-j]+temp+s[i+j]j+=1else:breakprint tempif len(temp)>m:m=len(temp)result=tempfor i in range(1,n):j=1temp=""while(i-j>=0 and i+j-1<n):if s[i-j]==s[i+j-1]:temp=s[i-j]+temp+s[i+j-1]j+=1else:breakprint tempif len(temp)>m:m=len(temp)result=tempreturn result

O（n）的算法，manacher算法。相当于对O（n2）算法的改进，O（n2）在判断过程中重复判断了相同的子串，效率较低。
具体解析可以参考曾会玩的文章，我觉得解释的很棒，容易理解。需要注意的一点就是 回文半径和下标，处理起来要小心一点。代码如下：

class Solution:"""@param: s: input string@return: the longest palindromic substring"""def longestPalindrome(self, s):# write your code heret=ss='#'+'#'.join(s)+'#'n=len(s)dp=[0]*n    #记录回文半径right=0;    #当前所有回文子串能达到的最右端字符下标pos=0;    #以right为最右端的回文子串的中心字符下标for i in range(n):if i>=right:dp[i]=1 else:if i+dp[pos-(i-pos)]<=right: #s[i]关于s[pos]对称的s[pos-(i-pos)]的回文半径+i和right相比dp[i]=dp[pos-(i-pos)]else:dp[i]=right-i+1while(i+dp[i]<n and i-dp[i]>=0 and s[i+dp[i]]==s[i-dp[i]] ):dp[i]+=1if dp[i]>right:pos=iright=dp[i]return s[pos-(dp[pos]-1):pos+(dp[pos]-1)+1].replace('#','')

这篇关于LintCode 最长回文子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---