本文共 2985 字，大约阅读时间需要 9 分钟。

题目

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

思路

1.中心扩散法：

枚举每一个位置（两个位置）作为中心点的情况，向两边扩散，不断更新最大长度的答案。

时间复杂度O(n^2)，空间复杂度O(1)。

2.动态规划：

定义状态dp[i][j]为区间[i,j]的s的子串是否为回文。假如dp[i][j]是回文，且s[i-1]==s[j+1]，那么dp[i-1][j+1]也是回文。在这个过程中不断更新最大长度的答案，最后输出这个最长的回文子串即可。

时间复杂度O(n^2)，空间复杂度O(n^2)。

比较：中心扩散法做了很多重复的判断，动态规划做法以空间换时间，记录下子串是否为回文的状态，虽然级别是一样的，但是实际上时间复杂度比中心扩散法低很多。

3.马拉车算法（Manacher）

Manacher算法是基于中心扩散法，采用以空间换时间的思路，将求最长回文子串的复杂度降到O(n)的巧妙方法。

思路：为了将长度为奇数的回文串和长度为偶数的回文串一起考虑，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现。用一个数组Len[i]表示以字符S[i]为中心的最长回文字串的最右字符到S[i]的长度，比如以S[i]为中心的最长回文字串是S[l, r]，那么Len[i] = r - i + 1。Len数组有一个性质，那就是Len[i] - 1就是该回文子串在原字符串S中的长度。

Len数组的计算：

设right为以字符S[i]为中心的最长回文字串的最右字符的位置，令pos为字符S[i]的位置i，i从左往右匹配。

存在两种情况：①当i < right时，我们把以pos为对称中心的与i对称的点即 j = 2 * pos - i。如果以j为中心的最长回文串在以pos为中心的最长回文串里，根据对称性得到 Len[i] = Len[j]；如果以j为中心的最长回文串不在以pos为中心的最长回文串里，说明超出这个范围了，那么根据对称性得到Len[i] = right - i。综上所述，Len[i] = min(right - i, Len[j])。

②当i>=right时，说明以T[i]为中心的回文串一个都没有进行匹配，所以Len[i]=1，需要从头开始一个个往下匹配。

时间复杂度O(n)，空间复杂度O(n)。

代码

// 中心扩散法class Solution {public:    string longestPalindrome(string s) {        int n = s.size();        if(n < 2) return s;        int ans = 1, bg = 0;        for(int i = 0; i < n - 1; i++) {            int left = i - 1, right = i + 1;            while(left >= 0 && right < n && s[left] == s[right]) {                if(right - left + 1 > ans) {                    ans = right - left + 1;                    bg = left;                }                left--;                right++;            }            if(s[i] == s[i + 1]) {                left = i, right = i + 1;                while(left >= 0 && right < n && s[left] == s[right]) {                    if(right - left + 1 > ans) {                        ans = right - left + 1;                        bg = left;                    }                    left--;                    right++;                }            }        }        return s.substr(bg, ans);    }};// 动态规划class Solution {public:    string longestPalindrome(string s) {        int n = s.size();        if(n < 2) return s;        int dp[n][n];        memset(dp, false, sizeof dp);        int ans = 1, bg = 0;        for(int i = n - 1; i >= 0; i--) {            for(int j = i; j < n; j++) {                if(j - i + 1 == 1) {                    dp[i][j] = true;                }                else if(j - i + 1 == 2) {                    if(s[i] == s[j]) {                        dp[i][j] = true;                        if(j - i + 1 > ans) {                            ans = j - i + 1;                            bg = i;                        }                    }                }                else {                    if(dp[i + 1][j - 1] && s[i] == s[j]) {                        dp[i][j] = true;                        if(j - i + 1 > ans) {                            ans = j - i + 1;                            bg = i;                        }                    }                }            }        }        return s.substr(bg, ans);    }};

转载地址：http://pefen.baihongyu.com/