最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

输入: "cbbd"
输出: "bb"

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s or len(s)==1:
            return s

        result = ''
        maxlen = 0
        for i in range(len(s)):
            for x in range(maxlen,len(s) - i):
                tsr = s[i:i+x+1]
                rtsr = tsr[::-1]
                if tsr == rtsr and len(tsr) > maxlen:
                    maxlen = len(tsr)
                    result = tsr

        return result

# manacher算法
def manacher(self):
        s = '#' + '#'.join(self.string) + '#'               # 字符串处理，用特殊字符隔离字符串，方便处理偶数子串
        lens = len(s)
        f = []                                          # 辅助列表：f[i]表示i作中心的最长回文子串的长度
        maxj = 0                                        # 记录对i右边影响最大的字符位置j
        maxl = 0                                        # 记录j影响范围的右边界
        maxd = 0                                        # 记录最长的回文子串长度
        for i in range(lens):                           # 遍历字符串
            if maxl > i:
                count = min(maxl-i, int(f[2*maxj-i]/2)+1)  # 这里为了方便后续计算使用count，其表示当前字符到其影响范围的右边界的距离
            else :
                count = 1
            while i-count >= 0 and i+count < lens and s[i-count] == s[i+count]:  # 两边扩展
                count += 1
            if(i-1+count) > maxl:                         # 更新影响范围最大的字符j及其右边界
                maxl, maxj = i-1+count, i
            f.append(count*2-1)
            maxd = max(maxd, f[i])                       # 更新回文子串最长长度
        return int((maxd+1)/2)-1                        # 去除特殊字符