关键词：
一、题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
二、解题
中心扩散法
中心扩散，找到基准点，向两边扩散查找，两边的值是否相等。分为奇数和偶数基准点。
找到最长长度的子串，返回起始点。
class Solution
public String longestPalindrome(String s)
if (s == null || s.length() < 1)
return "";
int maxLen = 0;
int begin = 0;
for(int i = 0;i<s.length();i++)
int len1 = extendSubstrings(s,i,i);
int len2 = extendSubstrings(s,i,i+1);
int curmaxLen = Math.max(len1,len2);
if(curmaxLen > maxLen)
maxLen = curmaxLen;
begin = i - (curmaxLen - 1)/2;
return s.substring(begin,begin+maxLen);
//回文串的长度
public int extendSubstrings(String s,int start,int end)
if(s.length() == 0)
return 0;
while(start>=0 && end < s.length() && s.charAt(start) == s.charAt(end))
start--;
end++;
return end - start - 1;
动态规划
dp[i][j]表示子串s[i…j]是否为回文子串。
状态转移方程：dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1]);
边界条件：j-1-(i+1)+1<2，整理为j-i<3；
初始化：dp[i][i] = true；
class Solution
public String longestPalindrome(String s)
if (s == null || s.length() < 1)
return "";
//动态规划
int length = s.length();
boolean[][] dp =new boolean[length][length];
int maxLen = 1;
int begin = 0;
//从左下角开始遍历
for(int j = 1;j<length;j++)
for(int i = 0;i<j;i++)
if(s.charAt(i) != s.charAt(j))
dp[i][j] = false;
else
if(j-i <3)
dp[i][j] = true;
else
dp[i][j] = dp[i+1][j-1];
if(dp[i][j] && j-i+1>maxLen)
maxLen = j-i+1;
begin = i;
return s.substring(begin,begin+maxLen);
代码二：
class Solution
public String longestPalindrome(String s)
if (s == null || s.length() < 1)
return "";
//动态规划
int length = s.length();
boolean[][] dp =new boolean[length][length];
int maxLen = 1;
int begin = 0;
for (int j = 0; j < length; j++)
for (int i = 0; i <= j; i++)
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]))
dp[i][j] = true;
if(dp[i][j] && j-i+1>maxLen)
maxLen = j-i+1;
begin = i;
return s.substring(begin,begin+maxLen);
马拉车算法
马拉车算法详细讲解看Manacher算法
class Solution
public String longestPalindrome(String s)
//马拉车算法
int length = s.length();
if(length < 2)
return s;
String str = addDividers(s,'#');
int sLen = 2*length+1;
//p[i] :以预处理字符串下标i为中心的回文半径（奇数长度是不包括中心）
//p是首字符。
int[] p = new int[sLen];
//通过中心扩散的方式能扩散的最右边的下标
int maxRight = 0;
//与maxRight对应的中心字符的下标
int center = 0;
int maxLen = 1;
int begin = 0;
int res = 0;
char[] charArray = str.toCharArray();
for(int i = 0;i<sLen;i++)
if(i < maxRight)
//状态转移方程
int mirror = 2 * center - i;
p[i] = Math.min(maxRight - i,p[mirror]);
//尝试使用中心扩散法 更新p[i]的值
int left = i - (1+p[i]);
int right = i + (1+p[i]);
while(left>=0 && right<sLen && charArray[left] == charArray[right])
p[i]++;
left--;
right++;
//更新maxRight，他是遍历过的i的i+p[i]的最大值
if(i+p[i] > maxRight)
//maxRight 和 center同时更新
maxRight = i + p[i];
center = i;
//统计答案，当前(p[i]+1)/2;
res += ((p[i]+1)/2) ;
//记录最长回文子串的长度和相应它在原始字符串的起点
if(p[i] > maxLen)
maxLen = p[i];
begin = (i - maxLen) / 2;
return s.substring(begin,begin+maxLen);
//预处理字符串
public String addDividers(String s,char divider)
if(s.indexOf(divider) != -1)
return null;
char[] charArray = s.toCharArray();
int length = s.length();
StringBuilder sb = new StringBuilder();
for(int i = 0;i<length;i++)
sb.append(divider);
sb.append(charArray[i]);
sb.append(divider);
return sb.toString();
马拉车算法详解(代码片段)
...Manacher算法，又称马拉车算法，它是用于求一个字符串的最长回文子串长度的算法，时间和空间复杂度为O(n)。算法思想 求一个字符串的最长回文子串长度，我们如果用暴力来做，我们就要取出这个串的所有子串，然后判断这... 查看详情
马拉车模板(代码片段)
马拉车算法介绍马拉车算法：得到以i为中心的最长子串的半径、找最长子串、找有多少个子串。详解用mx和id两个中间量来加快回文串匹配的过程，并且更新mx的最大值。mx为最大右边界，id为其中心，当i<mx时可以缩短求解过程... 查看详情
manacher'salgorithm马拉车算法
...马拉车算法Manacher‘sAlgorithm是用来查找一个字符串的最长回文子串的线性方法，由一个叫Manacher的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性，这是非常了不起的。对于回文串想必大家都不陌生... 查看详情
算法提升——中心扩散法（最长回文子串和回文子串）(代码片段)
中心扩散法常用来解决回文子串的问题，如最长回文子串和回文子串的问题。最长回文子串给你一个字符串s，找到s中最长的回文子串解题思路：从每一个位置确定回文子串中心点（回文子串向两边扩散的起始位... 查看详情
最长回文子串(动态规划法中心扩展算法)
问题描述：给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。思考：嗯，回文嘛！就是顺序读取和逆序读取的结果是一样的，那我们可以使用两个for循环来不断的截取给定的字符串S，然后判断截取后的... 查看详情
manacher马拉车算法(代码片段)
...助，解释的很详细。最近在学习lyd的算法竞赛书，学到求最长回文串的时候就看到了O(n)复杂度的Manacher算法，书上给的是hash+二分做法，复杂度为O(nlgn),所以我就去学习了一下Manacher算法.上面大佬的文章比较详细了，我在这里再... 查看详情
hdu3068最长回文（马拉车）(代码片段)
目录问题分析代码问题hdu3068最长回文-https://acm.hdu.edu.cn/showproblem.php?pid=3068分析暴力搜索（tle）马拉车O(n)代码暴力搜索#include<bits/stdc++.h>usingnamespacestd;constintMXN=1e5+10;chars[M 查看详情
hdu3068最长回文（马拉车）(代码片段)
目录问题分析代码问题hdu3068最长回文-https://acm.hdu.edu.cn/showproblem.php?pid=3068分析暴力搜索（tle）马拉车O(n)代码暴力搜索#include<bits/stdc++.h>usingnamespacestd;constintMXN=1e5+10;chars[M 查看详情
动态规划1.求最长回文子串(代码片段)
求字符串的子串大致有四中方法，暴力，DP，中心拓展，马拉车算法，这篇讲DP怎么做。DP最重要的就是要能利用到前面的结果来推断当前状态，比暴力优化的地方就在此，暴力需要对每一个字符串做一次O(n)的操作才能判断出结... 查看详情
manacher'salgorithm----马拉车算法
...我对博友 BIT祝威 和Grandyang ,以及寒小阳关于最长回文子串上关于马拉车算法理解的整理，若是对我的整理有所不懂得，建议去看BIT祝威的博客，很详细，以下纯属个人不成熟的理解。首先，得先了解什么是回文串（... 查看详情
马拉车模板
Input输入Str（Str的长度 <= 1000)Output输出最长回文子串的长度L。Input示例daabaacOutput示例5【模板】#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;charch[100100];charT[200200 查看详情
力扣5.最长回文子串(代码片段)
原题链接根据回文串的一个核心思想来解题：从中心点往两边扩散，来寻找回文串，这种方向相当于穷举字符串中每一个字符为中心点。假设回文串是奇数时，比如“bab”，它的中心点就只有一个“a”，... 查看详情
力扣5.最长回文子串(代码片段)
...。classSolution//主函数publicStringlongestPalindrome(Strings)//记录最长回文串Stringres="";//穷举以所有点（奇数一个点，偶数两个点）为中心的回文串for(inti=0;i<s.length();i++)//假设回文串是奇数时，由一个中... 查看详情
什么是马拉车算法（manacher'salgorithm）？(代码片段)
提出问题最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。如a、aa、aba、abba等。暴力解法简单粗暴：找到字符串的所有子串，遍历每一个子串以验证... 查看详情
最长回文子串的两个解法
...一下两种解法解法1：manachero(n)，扫一遍直接维护最长长度解法2：后缀数组将字符串倒序，然后拼到原字符串后面，直接用个符号隔开转化下题意，求拼接后的字符串某两个后缀的最长公共前缀，求下... 查看详情
动态规划—最长回文子串leetcode第5题深度剖析(代码片段)
动态规划对于笔者来说有很重要的意义一、题目如下：对于此类题目,笔者常用的的办法是先做个暴力解题思路,然后再对暴力法进行优化。二、暴力法//字串遍历publicstaticStringlongestPalindrome(Strings)Stringresult="";if(s.length()==1)returns;for(... 查看详情
力扣5-最长回文子串-（manacher算法）(代码片段)
题目：输出最长回文子串，原串最长1000坑：特判s="";复习一下马拉车算法，之前写的只求答案，没有要输出子串。classSolutionpublicStringlongestPalindrome(Strings)//特判s=""if(s.length()==0)returns;char[]a=newchar[20005];int[]p=newint[20005];//记录每个位... 查看详情
最长回文子串中心扩散详解(代码片段)
p(?,?)表示是否回文，并且第一个参数是左端点,第二个是右端点Si表示字符串中位置i对应的字符可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可... 查看详情