leecode 5. 最长回文子串 （马拉车算法）

本文主要是介绍leecode 5. 最长回文子串 （马拉车算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：leecode 5. 最长回文子串

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
**注意: "aba" 也是一个有效答案。**

示例 2：
输入: "cbbd"
输出: "bb"

可以参考博客

https://blog.csdn.net/the_star_is_at/article/details/53354958 (代码参考)

算法思路：Manacher算法

图片内容展示 主要是针对上面博客里面为何“当mx > i 时， p[i] = min(p[2 * id - i], mx - i) ”的理论解答；

算法实现：

class Solution {
public:string longestPalindrome(string s) {string sNew = "$#";for (auto iter = s.cbegin(); iter != s.cend(); iter++){sNew += *iter;sNew += "#";}int iNewSize = sNew.size();int iMaxSubStringLength = -1;    // 最长回文子串的半径int iMaxSubStringPos = -1; // 最长回文子串中心点的位置vector<int> p(iNewSize, 0);int id = 0;int mx = 0;//for循环内部为核心代码；for (int i = 1; i < iNewSize; i++){if (i < mx){p[i] = min(p[2 * id - i], mx - i);}else{p[i] = 1;}while (sNew[i - p[i]] == sNew[i + p[i]])  // 最左边sNew[0]='$',最右边sNew[sNew.size()] = '\0'，无需判断边界{p[i]++;}if (mx < i + p[i])  //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率  {id = i;mx = i + p[i];}if (p[i] - 1 > iMaxSubStringLength){iMaxSubStringLength = p[i] - 1;iMaxSubStringPos = i;}}
//for循环内部为核心代码；auto iStart = s.cbegin() + (iMaxSubStringPos - iMaxSubStringLength - 1) / 2; // 将最长回文子串起始位置转换回原串return string(iStart, iStart + iMaxSubStringLength);}
};

欢迎各位博友提问，以及对错误解释之处指出；

这篇关于leecode 5. 最长回文子串 （马拉车算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---