[数据结构与算法]最长回文子串(dp解法)

题目大意

题目传送门：https://leetcode-cn.com/problems/longest-palindromic-substring/
给你一个字符串，寻找其中最长回文子串并输出。

DP解法

首先对题目进行分析，这个最长的回文子串有什么特点？对于字符串str，假设dp[i,j]=1表示str[i…j]是回文子串，那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题，可以利用动态规划求解了。首先构造状态转移方程：

则整个方程的初始状态应该是这样的：

意思就是单个字符一定是一个回文串，连续两个相邻的相等字符也一定是回文串，比如“aa”。
这样就可以写出代码：

class Solution {
public:
        string longestPalindrome(string s) {
        if (s.empty()) return "";
        int len = s.size();
        if (len == 1)return s;
        int longest = 1;
        int start=0;
        int dp[1005][1005] = {0};
        for(int i = 0;i<len;i++)
        {
            dp[i][i] = 1;
            if(i<len-1)
            {
                if(s[i]==s[i+1])
                {
                    dp[i][i+1] = 1;
                    start = i;
                    longest = 2;
                }
            }
        }
        for(int l = 3;l<=len;l++)//子串的长度，范围是从3到len
        {
            for(int i = 0;i+l-1<len;i++)
            {
                int j = i+l-1;//终点
                if(s[i]==s[j] && dp[i+1][j-1]==1)
                {
                    dp[i][j] = 1;
                    start = i;
                    longest = l;
                }
            }
        }
        return s.substr(start,longest);
    }
};

另一种解法（Manacher）

一种专门用来解决此类问题的算法叫做“马拉车算法”，总体思想是“中心扩展”，由于回文子串的特性，遍历整个字符串，分别以每个字符作为对称轴向两边进行扩展，直至找到最长的回文子串。但是要注意回文子串长度为奇数和偶数的处理方法不太一样，具体的解释请参考：https://www.cxyxiaowu.com/2869.html中的方法三