最长回文子串（python，动规/马拉车）

思路1（动态规划，O(n^2)）
从第一个字符往后遍历，把每个字符都当作中心去向两边扩散，依次比较对称位置是否相等，当碰到左右边界停下。注意要分奇偶子串两种情况。

代码1

class Palindrome:
    def getLongestPalindrome(self, A, n):
        def func(A, left, right):
            while left >=0 and right < n and A[left]==A[right]:
                left -= 1
                right += 1
            return right-left-1

        res = 0
        for i in range(n-1):
            res = max(res, func(A, i, i), func(A, i, i+1))
        return res

思路2（马拉车算法，O(n)）
在处理最长回文子串的时候，一般教科书上都会提一个线性的算法–Manacher大法，它可以将动态规划情况下的复杂度由n^2的复杂度降到线性。马拉车算法能将奇偶长度的子串归为一类，统一使用上面动态规划用的中心扩展法。它在原字符串中插入特殊字符，例如插入#后原字符串变成'#3#5#5#3#4#3#2#1#'。现在我们对新字符串使用中心扩展发即可，中心扩展法得到的半径就是子串的长度。但是在本题实际操练时，耗时上并没卵用。这里简单看下思路吧。

代码2

class Palindrome:
    def getLongestPalindrome(self, A, n):
        if n <= 1: return n
        # 每个字符之间插入 #
        ss = '$#' + '#'.join([x for x in A]) + '#`'
        p = [1] * len(ss)
        center = 0
        mx = 0
        max_str = ''
        for i in range(1, len(p)-1):
            if i < mx:
                j = 2 * center - i # i 关于 center 的对称点
                p[i] = min(p[j],mx-i)
            # 尝试继续向两边扩展，更新 p[i]
            while ss[i - p[i] ] == ss[i + p[i] ]: # 不必判断是否溢出，因为首位均有特殊字符，肯定会退出
                p[i] += 1
            # 更新中心
            if i + p[i] - 1 > mx:
                mx = i + p[i] - 1
                center = i
            # 更新最长串
            if 2 * p[i]-1 > len(max_str):
                max_str = ss[i - p[i]+1 : i + p[i]]
        maxLen = len(max_str.replace('#', ''))
        return maxLen

麻豆出品，必出精品！