首页 > 代码库 > Longest Palindromic Substring
Longest Palindromic Substring
题目如下：
此题用Manacher算法求解，时间复杂度为O(n)
Python代码：
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ s = "#" + "#".join(s) + "#" print s i = 0 mx = 0 id = 0 p = [0 ] * len(s) while i<len(s): if mx > i: p[i] = min(p[ 2*id-i],mx-i) else: p[i] = 1 while i-p[i] >=0 and i+p[i] < len(s) and s[i-p[i]]==s[i+p[i]]: p[i] += 1 if mx < p[i]+i: mx = p[i] + i id = i i+=1 middle = p.index(max(p)) start = middle-(max(p)-2) end = middle+(max(p)-2)+1 rstr = ‘‘ for i in range(start,end,2): rstr += s[i] return rstr
Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。