解法1：暴力列举所有子数，再求回文数，时间复杂度O(n^3)
解法2：遍历所有字符，查找所有基于此字符的回文数，时间复杂度O(n^2)
解法3：manacher算法，时间复杂度O(n)。参考
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
manacher算法，先使用特殊符号间隔开所有字符,所得到的回文数就肯定是基数了
"""
l = len(s)
if l < 2: return s
newS = ""
for i in s:
newS = newS + "#" + i
newS = "$" + newS + "#"
newSl = len(newS)
p = []
p.append(1)
mx = 0
id = 0
max = 0
maxi = 0
# 以下计算出数组对应的i位置最长回文长度P数组
for i in range(1, newSl):
if mx > i :
p.append(min(p[2*id-i], mx-i))
else:
p.append(1)
while i + p[i] < newSl and newS[i + p[i]] == newS[i - p[i]]:
p[i] = p[i] + 1
if i+p[i] > mx:
mx = i + p[i]
id = i
if max < p[i]:
max = p[i]
maxi = i
#求出最大长度的回文数
if max < 2:
return s[2]
else:
left = maxi-(max-1)
right = maxi+max-1
r = newS[left:right]
r = r.replace('#', '')
return r
