最长回文子串和最长回文子序列（C++）

分别是Leetcode 5（最长回文子串）和Leetcode 516（最长回文子序列）原题，区别在于是否要求找到连续的回文串，解题算法涉及动态规划和著名的Manacher算法。

最长回文子串

问题描述

题目：输入一个字符串s，输出字符串中最长的回文子串。
示例：输入"abaca"，输出"aba"，或"aca"。

解法

方法一：动态规划

设置一个二维数组，维度为，表示字符串中到这一个子串是否是回文子串，和分别表示某个子串的两端，那么就可以将大问题分解为相似的小问题。
首先，每个字符单独可以作为一个回文串，在数组中表示即为对角线上的值（）都为。初始化之后，开始比较和的值：（1）若两值不相等，那么这段肯定就不是回文序列了，于是；（2）若两值相等，且两端字符中间的子串也是回文的话，那么加上两端字符的子串也是回文。这里还可以加上一点，要是的话，那么就不需要判断中间字符是否回文就可以直接断定这个子串是回文了。所以可以得到状态转移方程：

要注意的是，和的dp值会取决于和的dp值，所以从大到小遍历，则从小到大遍历。
因为题目求的是最长的回文子串，因此在每次找到回文串的时候，记录下此时和的值，最后得到差值最大的一组和，将其输出。
这种方法时间复杂度O(n^2)，空间复杂度O(n^2)。
Talk is cheap, show you the code：

string LongestPalindrome(string s){
    int len=s.length();
    if (len<2) return s;
    vector<vector<bool>>dp(len,vector<bool>(len, false));  //记录是否为回文的数组
    int left=0, right=0;
    for (int i=len-1;i>=0;i--){
        dp[i][i]=true;
        for (int j=i+1;j<len;j++){
            if (s[i]==s[j]&&(j-i<3||dp[i+1][j-1])){  //状态转移条件
                dp[i][j]=true;
                if (j-i>left-right){  //得到最大的那个回文串
                    left=i;
                    right=j;
                }
            }
        }
    }
    return s.substr(left, right-left+1);
}

方法二：Manacher算法

马拉车算法，最大的贡献是将时间复杂度降低到了线性，它的核心思想是每个字符的中心扩展，也就是从把每个字符或者每两个字符中间当作回文串的中心，再向左右两边延伸，判断左右对称的字符是否相等。在这个基础上加了两个优化操作：一是把字符串每两个字符中间都加一个'#'，这样得到的字符串长度都为奇数了，避免了区别奇偶长度；二是增加了一个右边界，当要判断的中心字符位于最大右边界之内（位于右瓣）时，可以通过回文串对称的特性，找到与当前字符对称的点（位于左瓣），通过对称点的回文特性省去一些不必要的计算，详细解释点这里。
具体代码中设置了一个p矩阵，代表以第个字符为中心时，回文串的半径长度，为了避免将前后的'#'也配对。
这个算法时间复杂度O(n)，空间复杂度O(n)。

string Manacher(string s) {
    string t = "$#";     //字符串预处理
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;   //判断当前字符中心是否在最大右边界之内
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {  //更新回文串的最大半径
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

最长回文子序列

问题描述

题目：输入一个字符串s，输出字符串中最长的回文子序列长度
示例：输入"abacaa"，输出5（"aacaa"）。

解法

动态规划

和找最大回文串类似，设置一个二维数组，维度为，表示字符串中到这一个子串中回文序列的长度，和分别表示某个子串的两端，那么就可以将大问题分解为相似的小问题。
每个字符单独可以作为一个回文序列，在数组中表示即为对角线上的值（）都为1。初始化之后，开始比较和的值：（1）当两值相等时，如果和之间的子串也是回文序列，那么加上两端字符之后也是回文序列，因此序列值加2；（2）若两值不相等，需要看到之间以及到之间的子串是否是回文序列，其中一个是的话，加上两端字符之后也是回文序列，但序列长度不变。所以可以得到状态转移方程：

同样的，和的dp值会取决于和的dp值，所以从大到小遍历，则从小到大遍历。
这种方法时间复杂度O(n^2)，空间复杂度O(n^2)。

int LongestPalindromeSubseq(string s){
    int len=s.length();
    if (len<2) return len;
    vector<vector<int>> dp(len, vector<int>(0));
    for (int i=len-1;i>=0;i--){
        dp[i][i]=1;
        for (int j=i+1;i<len;j++){
            if (s[i]==s[j]){
                dp[i][j]=dp[i+1][j-1]+2;
            }else{
                dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][len-1];
}

参考

Manacher算法：https://blog.csdn.net/u011469138/article/details/82431327