小算法：最长回文子串

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

示例 1：

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

示例 2：

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

---

中心扩展算法

只需使用恒定的空间，可以在 的时间内解决这个问题

观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。

为什么会是 2n−1 个中心？因为所含字母数为偶数的回文中心处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）。

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        str = ""
        for i in range(2*len(s)-1):
            if i%2 == 0:
                start = end = i // 2
            else:
                start = (i-1) // 2
                end = (i+1) //2
            while start>=0 and end<len(s) and s[start]==s[end]:
                start -= 1
                end += 1
            if len(str) <= (end-start-1):
                str = s[start+1:end]
        return str

---

Manacher 算法

很神奇，可以在 时间内解决

详细过程移步：https://articles.leetcode.com/longest-palindromic-substring-part-ii/