题目描述：

给定字符串$S$，求其最长的回文子串。

Leetcode:https://leetcode.com/problems/longest-palindromic-substring/

下面给出四种算法思路，分别是朴素枚举、动态规划、中心拓展和Manacher算法。

其中，Manacher算法复杂度为$O(n)$

1. 朴素枚举

时间复杂度：$O(n^3)$

枚举$S$的所有子串，判断子串是否为回文字符串，取其中最长子串。

def palindrome1(s):
    n = len(s)
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            if j-i+1>ans and s[i:j]==s[j:i:-1]:
                ans = j-i+1
    return ans

2. 动态规划

时间复杂度：$O(n^2)$

注意到枚举子串并判断时产生了大量的重复判断，用状态$dp[i][j]$记录子串$s[i:j]$是否为回文字符串。枚举子串时按照子串长度的顺序进行枚举，若$s[i+1:j-1]$是回文串并且$s[i]==s[j]$，那么$s[i:j]$也是回文串。

def palindrome2(s):
    n = len(s)
    dp = [[False for i in range(n)]for i in range(n)]
    for i in range(n):
        dp[i][i] = True
        dp[i][i-1] = True
    ans = 0
    for l in range(2,n+1):
        for i in range(n-l+1):
            j = i+l-1
            if dp[i+1][j-1] and s[i]==s[j]:
                dp[i][j] = True
                ans = l
    return ans

3. 中心拓展

时间复杂度：$O(n^2)$

回文串都是以中心对称的，因此可以枚举回文串的中心，再从中心向两边拓展找出当前中心的最长子串。注意中心可以是字符，也可以是字符之间的间隙，为了方便起见，将字符串的字符之间都插入一个特殊符号便于处理，例如”ABC”变为”A_B_C“。

def palindrome3(s):
    s = "".join(map(lambda x:'_'+x,s))+'_'
    n = len(s)
    ans = 0
    for i in range(n):
        l = r = i
        while l-1 >= 0 and r+1 < n and s[l-1]==s[r+1]:
            l -= 1
            r += 1
        ans = max(ans,r-l+1)
    return ans/2

4. Manacher算法

时间复杂度：$O(n)$

Manacher算法是由Manacher在1975年提出的，算法的思想也是从左到右依次计算以当前字符为中心的最大回文串，但在计算时利用了回文子串的特殊性质来减少计算量。

假设已知$S$的两个回文子串$S1$，$S2$，其回文中心字符的位置分别为$c1$，$c2$（$c1$ < $c2$，$c1$在$c2$的左侧），并且$S1$又是$S2$的子串。由于$S2$是回文串，因此$S2$中的任一子串在以$c2$为对称轴的右侧也有完全相同的子串。根据这一性质，存在$S3$为$S2$的子串，并且$S3$和$S1$完全相同并以$c2$为对称轴对称。那么$S3$也同样是回文串，其对称中心为$2*c2-c1$。并且若$S1$不是$S2$的前缀，或者$S2$是$S$的后缀的情况下，以$2*c2-c1$对称的最大回文子串可以直接确定为在$S2$中与$S1$完全对称的子串。

因此，当确定了当前中心$c1$的最大回文子串$S1$后，设其长度$l1$，向右去找在$S1$内可以直接确定的最大回文子串的对称中心，这些对称中心则可以直接跳过而不去计算。只有当回文串不能直接确定时，才需要进一步比较确定该中心的最大回文子串。

完整的算法如下：

#length[i] 表示以第i个字符为中心的最大回文串长度
1. 当前中心c = 1
2. 循环以下步骤直到c不合法：
    a. 从两端同时扩展得到以c为中心的最长回文子串，其长度为l,length[c] = l
    b. i = 1,2,..;当length[c-i]所代表的子串是length[c]的子串，且不为length[c]的前缀或者length[c]是原字符串的后缀时，length[c+i]可以直接确定为length[c-i]。即根据length[c-1],length[c-2]...的值来更新可以确定的最长回文子串长度length[c+1],length[c+2]...直到不能确定其回文长度的中心为c+i
    c. 令当前中心c = c+i

同样也需要在字符中插入特殊字符在处理中心为间隙的情况。

def palindrome4(s):
    s = "".join(map(lambda x:'_'+x,s))+'_'
    n = len(s)
    length = [0 for i in range(n)]
    c = 0
    while c < n:
        l = c-length[c]/2
        r = c+length[c]/2
        while l-1 >= 0 and r+1 < n and s[l-1]==s[r+1]:
            l -= 1
            r += 1
        length[c] = r-l+1
        i = 1
        # 能确定以c+i为中心的最长子串的长度
        while c-i >= 0 and c+i < n and c-i-length[c-i]/2>c-length[c]/2 or\
             (c-i-length[c-i]/2==c-length[c]/2 and c+length[c]/2==n-1):
            length[c+i] = length[c-i]
            i += 1
        # 不能确定以c+i为中心的最长子串的长度，但能确定其至少大于length[c-i]
        if c-i >= 0 and c+i < n and c-i-length[c-i]/2==c-length[c]/2:
            length[c+i] = length[c-i]
        c = c + i
    return max(length)/2

时间复杂度证明：

考虑内循环中字符的总比较次数，每次比较的右端字符都在前次比较过的右端字符的后面，也就是说右端字符并没有重复，而右端字符最多有$n$个位置，字符比较次数最多为$n$次
考虑内循环中确定$length[c+i]$的次数，因为$length$最多有$n$个值，确定$length[c+i]$不会重复访问，因此确定$length[c+i]$最多为$n$次。

综上，时间复杂度为$O(n)$

最长回文子串Longest palindromic substring的四种算法