题解 | #最长回文子串#

题目主要信息：

• 给定一个仅包含小写字母的字符串，求它的最长回文子串的长度
• 回文串，指左右对称的字符串

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM66.最长公共子串

BM71.最长上升子序列(一)

BM75 编辑距离(一)

BM76 正则表达式匹配

BM77 最长的括号子串

方法一：中心扩展法（推荐使用）

知识点：贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

思路：

回文串，有着左右对称的特征，从首尾一起访问，遇到的元素都是相同的。但是我们这里正是要找最长的回文串，并不事先知道长度，怎么办？判断回文的过程是从首尾到中间，那我们找最长回文串可以逆着来，从中间延伸到首尾，这就是中心扩展法。

具体做法：

• step 1：遍历字符串每个字符。
• step 2：以每次遍历到的字符为中心（分奇数长度和偶数长度两种情况），不断向两边扩展。
• step 3：如果两边都是相同的就是回文，不断扩大到最大长度即是以这个字符（或偶数两个）为中心的最长回文子串。
• step 4：我们比较完每个字符为中心的最长回文子串，取最大值即可。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int fun(String s, int begin, int end){
        //每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){ 
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1; 
    } 
    public int getLongestPalindrome (String A) {
        int maxlen = 1;
        //以每个点为中心
        for(int i = 0; i < A.length() - 1; i++) 
            //分奇数长度和偶数长度向两边扩展
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
}

C++实现代码：

class Solution {
public:
    int fun(string& s, int begin, int end){
        //每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s[begin] == s[end]){ 
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1; 
    } 
    int getLongestPalindrome(string A) {
        int maxlen = 1;
        //以每个点为中心
        for(int i = 0; i < A.length() - 1; i++) 
            //分奇数长度和偶数长度向两边扩展
            maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
};

Python代码实现：

class Solution:
    def fun(self, s: str, begin: int, end: int) -> int:
        #每个中心点开始扩展
        while begin >= 0 and end < len(s) and s[begin] == s[end]: 
            begin -= 1
            end += 1
        #返回长度
        return end - begin - 1 
    def getLongestPalindrome(self , A: str) -> int:
        maxlen = 1
        #以每个点为中心
        for i in range(len(A) - 1): 
            #分奇数长度和偶数长度向两边扩展
            maxlen = max(maxlen, max(self.fun(A, i, i), self.fun(A, i, i + 1)))
        return maxlen

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$为字符串长度，遍历字符串每个字符，每个字符的扩展都要$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间

方法二：manacher算法（扩展思路）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

方法一讨论了两种情况，子串长度为奇数和偶数的情况，但其实我们可以对字符串添加不属于里面的特殊字符，来让所有的回文串都变成奇数形式。同时上述中心扩展法有很多重复计算，manacher就可以优化：

具体做法：

• step 1：我们用maxpos表示目前已知的最长回文子串的最右一位的后一位，用index表示当前的最长回文子串的中心点。
• step 2：对于给定的 i 我们找一个和它关于index对称的 j ，也就是$index-j==i-indexindex-j\; ==\; i-index$，换言之就是$j==2\ast index-ij==2*index-i$。
• step 3：i 和 j 的最长回文子串在index的回文串范围内的部分应该是一模一样的，但是在外面的部分就无法保证了，当然，最好的情况是i和j的回文子串范围都很小，这样就保证了它们的回文子串一定一模一样，对于超出的部分我们也没有办法, 只能手动使用中心扩展。
• step 4：最后答案计算的时候需要考虑使用预处理，长度被加了一倍，于是结果是 max(mp[i]-1)。

Java实现代码：

import java.util.*;
public class Solution {
    //manacher算法
    public void manacher(String s, int n, int[] mp){ 
        String ms = "";
        ms += "$#";
        //预处理
        for(int i = 0; i < n; i++){ 
            //使之都变成奇数回文子串
            ms += s.charAt(i); 
            ms += '#';
        }
        //目前已知的最长回文子串的最右一位的后一位
        int maxpos = 0; 
        //当前的最长回文子串的中心点
        int index = 0; 
        for(int i = 0; i < ms.length(); i++){ 
            mp[i] = maxpos > i ? Math.min(mp[2 * index - i], maxpos - i) : 1; 
            while(i - mp[i] > 0 && i + mp[i] < ms.length() && ms.charAt(i + mp[i]) == ms.charAt(i - mp[i])) 
                //两边扫
                mp[i]++;
            //更新位置 
            if(i + mp[i] > maxpos){ 
                maxpos = i + mp[i];
                index = i;
            }
        }
    }
    public int getLongestPalindrome (String A) {
        int n = A.length();
        //记录回文子串长度
        int[] mp = new int[2 * n + 2]; 
        manacher(A, n, mp);
        int maxlen = 0;
        //遍历数组
        for(int i = 0; i < 2 * n + 2; i++) 
            //找到最大的长度
            maxlen = Math.max(maxlen, mp[i] - 1);  
        return maxlen;
    }
}

C++实现代码：

class Solution {
public:
    //manacher算法
    void manacher(string& s, int n, vector<int>& mp){ 
        string ms = "";
        ms += "$#";
        //预处理
        for(int i = 0; i < n; i++){ 
            //使之都变成奇数回文子串
            ms += s[i]; 
            ms += '#';
        }
        //目前已知的最长回文子串的最右一位的后一位
        int maxpos = 0; 
        //当前的最长回文子串的中心点
        int index = 0; 
        for(int i = 0; i < ms.length(); i++){ 
            mp[i] = maxpos > i ? min(mp[2 * index - i], maxpos - i) : 1; 
            //两边扫
            while(ms[i + mp[i]] == ms[i - mp[i]]) 
                mp[i]++;
            //更新位置
            if(i + mp[i] > maxpos){ 
                maxpos = i + mp[i];
                index = i;
            }
        }
    }
    int getLongestPalindrome(string A) {
        int n = A.length();
        //记录回文子串长度
        vector<int> mp(2 * n + 2); 
        manacher(A, n, mp);
        int maxlen = 0;
        //遍历数组
        for(int i = 0; i < 2 * n + 2; i++) 
            //找到最大的长度
            maxlen = max(maxlen, mp[i] - 1);  
        return maxlen;
    }
};

Python代码实现：

class Solution:
    #manacher算法
    def manacher(self, s: str, n: int, mp: List[int]): 
        ms = ""
        ms += "$#"
        #预处理
        for i in range(n): 
            #使之都变成奇数回文子串
            ms += s[i] 
            ms += '#'
        #目前已知的最长回文子串的最右一位的后一位
        maxpos = 0 
        #当前的最长回文子串的中心点
        index = 0 
        for i in range(len(ms)):
            if maxpos > i:
                mp[i] = min(mp[2 * index - i], maxpos - i)
            else:
                mp[i] = 1
            #两边扫
            while i - mp[i] > 0 and i + mp[i] < len(ms) and ms[i + mp[i]] == ms[i - mp[i]]: 
                mp[i] += 1
            #更新位置
            if i + mp[i] > maxpos: 
                maxpos = i + mp[i]
                index = i      
    def getLongestPalindrome(self , A: str) -> int:
        n = len(A)
        #记录回文子串长度
        mp = [0 for i in range(2 * n + 2)] 
        self.manacher(A, n, mp)
        maxlen = 0
        #遍历数组
        for i in range(2 * n + 2): 
            #找到最大的长度
            maxlen = max(maxlen, mp[i] - 1)  
        return maxlen

复杂度分析：

• 时间复杂度：$O(n)O(n)$，都是单层遍历，函数中的while循环累计也不会超过$2n2n$次
• 空间复杂度：$O(n)O(n)$，长度为$2\ast n2*n$的预处理后的字符串和长度为$2\ast n+22*n+2$的数组