给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
思路：manacher算法模板题
manacher算法是对朴素的回文串搜索的优化，只需要O(n)的时间复杂度就可以计算最长回文串。
代码：
class Solution:
def longestPalindrome(self, s: str) -> str:
if s=="":
return ""
index=[0,1]
mid=1
r=1
a=['#']
for i in s:
a.append(i)
a.append('#')
l=len(a)
ll=0
for i in range(2,l):
if i<mid+r:
ll=min(index[2*mid-i],mid+r-i)
else:
ll=0
if i+ll>=mid+r:
j=1
while i+ll+j<l and i-ll-j>=0 and a[i+ll+j]==a[i-ll-j]:
j+=1
ll=ll+j-1
if i+ll>mid+r:
mid=i
r=ll
index.append(ll)
ans=""
num=max(index)
mnum=0
for i in range(len(index)):
if index[i]==num:
mnum=i
break
start=0
if num%2==0:
start=int((mnum)/2-num/2)
else:
start=int((mnum+1)/2-(num-1)/2)-1
for i in range(start,start+num):
ans+=s[i]
return ans