最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

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

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

Manacher’s algorithm

核心思想：通过插入其他的字符，将回文串变为奇回文串。奇回文串一定存在一个中心点loc，对应的有一个半径p[loc]。从左往右遍历，关于每个节点都用扩张法（也就是不断判断两边的边缘是否相同，相同则不断增加） 来得到以它为中心的最长回文子串的边界长度来更新所对应的p[i]。然后，记录下当前 边界最右 的回文子串（即，记录下中心位置loc,以及对应的边界mx）。注意一个非常重要的细节：对于在当然记录下的loc右边的点，明显由于奇回文串的对称性， 能够知道该店关于loc的对称点的半径长度的最小值p[2* loc -i] 。而当然，它也会受到边界mx的限制，在i和mx之间的点，由于对称点的信息基本可以保证不用判断，就算需要判断，但是由于对称性，落入其中一定是因为不能再扩张了，（这点保证了算法时间复杂度被约束在了O(n)） ，而在mx以外的点，仍然需要用扩张法来扩张对应的半径，（这样虽然是二重循环，但是，第二重只是对于mx以外的点进行了判断，因此仍然是O(n）。

代码

#define min(x, y) ((x)>(y)?(y):(x))class Solution { public:string regenerate_str(string s) { // 插入string t("#");int count=0;for (int i = 0; i < s.size() * 2 + 1; ++i) {if (i % 2 == 0) { t += s[count++]; }else t += "#";}return t;}string longestPalindrome(string s) {if (s.size() < 2) return s;s = regenerate_str(s);int p[2002], start = 0, maxlen = 0;int mx = 0, loc = 0;for (int i = 0; i < s.size(); ++i) {if (i < mx && 2 * loc - i < s.size()) {p[i] = min(mx - i, p[2 * loc - i]);}else {p[i] = 1;}while (p[i] + i < s.size() && i - p[i] >= 0 && s[i - p[i]] == s[i + p[i]])p[i] ++;if (i + p[i] > mx) {mx = i + p[i];loc = i;}if (p[i] > maxlen) { maxlen = p[i]; start = i; }}s = s.substr(start - p[start] + 1, 2 * p[start] - 1);string t;for (int i = 0; i < s.size(); ++i) {if (s[i] != '#') t.push_back(s[i]);}return t;} };

总结

以上是生活随笔为你收集整理的Manacher's algorithms（马拉车算法）最长回文子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。