最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
可以借助Manacher's Algorithm（马拉车算法）进行求解
这个算法是以每一个字符为中心, 向两边发散,同时,用一个数组p来记录以每一个字符为中心的回文串的一半的长度.
具体的可网上检索进行了解
代码如下：
class Solution:
def longestPalindrome(self, s):
def get_length(string, index):
# 借助循环求出index为中心的最长回文字串
start, length = index // 2, 0
#获取字符串长度，并赋值非r_
r_ = len(string)
for i in range(1, index + 1):
if index + i < r_ and string[index - i] == string[index + i]:
start = (index - i) // 2
length += 1
else:
break
return start, length
s_list = [c for c in s]
# 形成新串
new_s = '#' + '#'.join(s_list) + '#'
#初始化赋值
max_start = max_length = 0
length = len(new_s)
for index in range(0, length):
start, r_length = get_length(new_s, index)
if max_length < r_length: #如果max_length小于r_length 则将start、r_length分别赋值给max_start、max_length
max_start, max_length = start, r_length
return s[max_start: max_start+max_length]