最长回文子串 python

以下是两种求解最长回文子串的方法：

1. 方法三：根据回文串对称性，分为奇数长度回文串和偶数长度回文串

def match(s):
    res = 0
    for i in range(len(s)-1):
        if s[i] == s[i+1]: # 奇数长度
            first = i
            end = i+1
            while first >= 0 and end < len(s) and s[first] == s[end]: # 满足条件就向两边扩展
                first -= 1
                end += 1
            res = max(res, end-first-1)
        elif s[i-1] == s[i+1]: # 偶数长度
            first = i-1
            end = i+1
            while first >= 0 and end < len(s) and s[first] == s[end]:
                first -= 1
                end += 1
            res = max(res, end-first-1)
    return res

match('abba') # 输出：4

2. 方法四：Manacher算法

def longestPalindrome(s):
    T = '#'.join('^{}$'.format(s))
    n = len(T)
    P = [0] * n
    C = R = 0
    for i in range(1, n-1):
        if R > i:
            P[i] = min(R-i, P[2*C-i])
        while T[i+1+P[i]] == T[i-1-P[i]]:
            P[i] += 1
        if i + P[i] > R:
            C = i
            R = i + P[i]
    maxLen = max(P)
    centerIndex = P.index(maxLen)
    start = (centerIndex - maxLen) // 2
    return s[start:start+maxLen]

longestPalindrome('abba') # 输出：'abba'