给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：
输入: “cbbd” 输出: “bb”
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
本题主要的解法有三种。 一是暴力求解，复杂度是O(n^3) 二是动态规划，复杂度是O(n^2) 三是manacher方法，复杂度是O(n) 主要说一下动态规划跟manacher方法。
动态规划 1、用dp[i][j]表示s[i…j]是否是回文字符串，如果是，则dp[i][j]=1，否则为0 2、那么dp[i][j]的更新算法是： 如果s[i]==s[j]，则dp[i][j]=dp[i+1][j-1] 如果s[i]!=s[j]，则dp[i][j]=0 此外，如果i与j的差值小于等于2，那么在s[i]==s[j]的情况下，dp[i][j]直接赋为1 代码如下：
class Solution { public: string longestPalindrome(string s) { if(s.size()<2) return s; int** dp=new int*[s.size()]; for(int i=0;i<s.size();i++) dp[i]=new int[s.size()]; for(int i=0;i<s.size();i++) dp[i][i]=1; int max_len=1; int l,r; l=0;r=0; for(int j=1;j<s.size();j++) { for(int i=j-1;i>=0;i--) { if(s[i]==s[j]) { if((j-i)<=2) dp[i][j]=1; else dp[i][j]=dp[i+1][j-1]; } else dp[i][j]=0; if(dp[i][j]==1&&(j-i+1)>max_len) { max_len=j-i+1; l=i;r=j; } } } string result(s,l,max_len); return result; } };manacher方法 manacher方法的主要思路是首先在原字符串s的基础上插入通用字符，使得字符串长度为奇数偶数时能统一处理，做法是选取s中没出现的字符，一般用“#”，在s的首尾以及每两个字符中间插入“#”， eg: s: “abc” 处理后： t “#a#b#c#”
处理后之后计算len数组，len数组中len[i]表示字符串t中以t[i]为中心的最长回文字符串最右位置到i的长度，在更新len数组时，从i=2开始，用max_r表示从0到i-1为中心的回文字符串所能到达的最右边的位置，用pos标记取得这个位置max_r时的中心点位置。 代码
class Solution { public: string longestPalindrome(string s) { if(s.size()<2) return s; string t; t="#"; for(int i=0;i<s.size();i++) { t+=s[i]; t+="#"; } int* len=new int[t.size()]; int pos,max_r,max_len,max_pos; pos=1; max_r=1; max_len=1; max_pos=1; len[0]=1; len[1]=1; for(int i=2;i<t.size();i++) { len[i]=1; if(max_r>i) len[i]=len[2*pos-i]<(max_r-i+1)?len[2*pos-i]:(max_r-i+1); while((i-len[i])>=0&&t[i+len[i]]==t[i-len[i]]) len[i]++; if((i+len[i]-1)>max_r) { max_r=i+len[i]-1; pos=i; } if(len[i]>max_len) { max_len=len[i]; max_pos=i; } } return s.substr((max_pos-max_len+1)/2,len[max_pos]-1); } };提交结果
