Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
1 class Solution: 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 # preprocess 8 slist = list(s) 9 for i in range((len(s) + 1) * 2)[::2]: 10 slist.insert(i, "#") 11 slist.insert(0, ‘$‘) 12 13 p = self.manacher(slist) 14 15 i = p.index(max(p)) 16 ans = ‘‘.join(slist[i-p[i]+1:i+p[i]]) 17 return ans.replace(‘#‘,‘‘).replace(‘$‘,‘‘) 18 def manacher(self, slist): 19 20 21 # 计算p 22 p = [0] * len(slist) 23 p[0] = 1 24 id = 0 25 mx = 1 26 print(slist) 27 for i in range(1,len(slist)): 28 if mx > i: 29 p[i] = min(p[id * 2 - i], mx - i) 30 else: 31 p[i] = 1 32 33 #暴力 34 while i +p[i]<len(slist) and slist[i - p[i]]==slist[i + p[i]]: 35 p[i] = p[i]+1 36 #更新最大三元组 37 if(mx < i + p[i]): 38 mx = i + p[i] 39 id = i 40 41 return p