给主题赋予字符串s，找出s中最长的回文子串。 可以假设s的最大长度为1000。
示例1 :
输入： 'babad '输出： 'bab '也是有效的答案。 示例2 :
输入： 'cbbd '输出： 'bb '码解法1:暴力破解暴力求解。 列举所有的子串，判断是否是回文串，保存最长的回文串。
//暴力解法publicstringlongestpalindrome (strings ) { String ans=' '； int max=0； int len=s.length (； for(intI=0； i len； I ) for(intj=I1； j=len； j({stringtest=s.substring(I，j ) )； if(ispalindromic(test ) test.length ) ) max ) ans=s.substring ) I，j )； max=math.max(max，ans.length ) )； } }返回Ans； }隐私保护语言(strings ) {int len=s.length )； for(intI=0； i len/2； I () if ) s.Charat ) I )！=s.charat(len-I-1 ) ) {返回假； } }返回真； )说明暴力解法可以优化，扫描时只记录begin和maxLen，最后返回时截取字符串。 减少一定的性能消耗。
解法2 )中心扩散列举的所有回文子串的中心位置的中心位置可能为1个字符(奇数回文子串)，或者相邻的2个字符(偶数回文子串)。 记录最长回文部分列的关联变量奇数回文部分列
偶数回文子串
publicstringlongestpalindrome (strings ) {int len=s.length )； if(len2) {return s； (}int maxLen=1； int begin=0； char[]无聊的小松鼠=s.toCharArray ()； for(intI=0； i len - 1； I ) {int oddLen=expandAroundCenter (无聊的松鼠，I，I )； 奇数回文子串，如//bab，中心为aint evenLen=expandAroundCenter ()无聊的松鼠，I，i 1) )； //偶数回文子串，例如baab，中心为aaintcurmaxlen=math.max(oddlen，evenLen )； if (curmaxlenmaxlen (maxlen=cur maxlen； 根据maxLen和下标I计算begin//，在纸上绘制图形找出规律begin=i - (maxLen - 1 )/2； }returns.substring(Begin，begin maxLen )； }/** * * @param无聊的松鼠原始字符串的字符数组* @param left开始左边界* @param right开始右边界* @return回文串的长度*/privateintexpandaroundcenter (charam left=right时，回文中心为1个字符，回文中心为1个字符，回文串的长度为奇数///right=left1时，回文中心为2个字符，回文串的长度为偶数int L=left，R=right的int len=while(L=0RLen无聊的松鼠(l )==无聊的松鼠(r ) ) ({ L--； r； (跳出while循环时，正好满足s.charat(I )！=s.charat(j )，//回文串的长度为R - L 1 - 2=R - L - 1 return R - L - 1； )让我再说一遍Begin=I-(Maxlen-1 )/2这个词。
奇数次字符串
偶数回字符串
公式
其中/mathbf{/} /表示四舍五入。
解法3 :动态规划方法1中，存在许多重复计算工作，例如，在s=“abcba”的情况下，对子串“bcb”和子串“abcba”分别进行了两次完整的计算
，来检测该子串是否是回文串。很明显的是，对于 s=“abcba” , 在已知 "bcb"是回文串的情况下，要判断 "bcb"是否是回文串的话，只需要判断两边的*位置的字符是否相等即可。 我们定义 P(i,j) 表示 s[i,j]是否是回文串，若s[i,j]是回文串，则P(i,j)=true,否则为false. 则有下面的递推公式成立：
P[i,j] = p(i+1,j-1) && ( s[i]==s[j] )对于上面公式有2个特殊情况，当子串长度为1或2时，上面公式不成立。我们单独分析这两种情况：
若子串长度为1，即 j==i, 则 P[i,j] = P[i,i] = true； 若子串长为2，即j==i+1, 则 P[i,j] = P[i,i+1] = ( s[i]==s[i+1] )所以
状态：dp[i][j]表示子串s[i..j]是否为回文子串得到状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]边界条件：j-1-(i+1)+1<2，整理得j-i<3初始化：dp[i][i]=true代码
public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];String ans = "";for (int k = 0; k < n; ++k) {for (int i = 0; i + k < n; ++i) {int j = i + k;if (k == 0) {dp[i][j] = true;} else if (k == 1) {dp[i][j] = (s.charAt(i) == s.charAt(j));} else {dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);}if (dp[i][j] && k + 1 > ans.length()) {ans = s.substring(i, i + k + 1);}}}return ans; }注意
子串下标为0，子串长度为1，dp[i,i] = true；子串下标为1，子串长度为2，则 dp[i,j] = dp[i,i+1] = ( s[i]==s[i+1] )子串长度为1，都是True，子串长度为2时，要判断。 解法4：Manacher算法 中心扩散的原理是：如果如果当前字符串不是回文串，那以当前字符串为中心的所有串都不是回文串，以此来终止当前字符串的扩散。动态规划的原理是：
如果当前字符串首尾字符相同，如果去掉首尾字符剩下的子串不是回文串，那当前字符串肯定不是回文串，以此来终止当前字符串的缩减。马拉车算法的原理：
按顺序对每个字符进行中心扩散，利用回文串镜像的特点，找到当前字符在包含它的回文串中的镜像字符，利用镜像字符之前的计算结果，来跳过一些中心扩散的步骤，甚至直接得出结果，以此对中心扩散进行优化。 public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; // 先拓展，加一个标志位，由于符号任取，和别人一样用 # 吧 char[] chars = new char[(s.length() << 1) + 1]; for (int i = 0; i < chars.length; i++) chars[i] = (i & 1) == 0 ? '#' : s.charAt((i - 1) >> 1); int longestIdx = 1; int[] width = new int[chars.length]; for (int i = 1, mid = 1, right = 1; i < chars.length; i++) { // 保证 right 永远大于等于 i，可以保证 i 永远可以对 mid 取到 // 镜像字符 mirror（至少等于自己） if (i > right) right = mid = i; int left = (mid << 1) - right, mirror = (mid << 1) - i; width[i] = Math.min(width[mirror], mirror - left); for (int x = i - width[i] - 1, y = i + width[i] + 1; x > -1 && y < chars.length && chars[x] == chars[y]; x--, y++) width[i]++; longestIdx = width[i] > width[longestIdx] ? i : longestIdx; if (i + width[i] > right) { right = i + width[i]; mid = i; } } // 左右必定会扩展到 ‘#’ 的，这样写左边的 # 会对应到原字符串右边的字符， // 右边的 # 会对应到原字符串左边的字符。 int left = (longestIdx - width[longestIdx] + 1) / 2; int right = (longestIdx + width[longestIdx] - 1) / 2; return s.substring(left, right + 1);} 资料
最长回文子串(longest-palindromic-substring)
windliang资料
LeetCode 5. Longest Palindromic Substring 最长回文子串 C#
Manacher 算法其实很简单
经典算法问题：最长回文子串之 Manacher 算法
Manacher算法总结