本文共 1518 字，大约阅读时间需要 5 分钟。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。
示例:
输入: "babad"输出: "bab"注意: "aba"也是有效答案
示例:
输入: "cbbd"输出: "bb"
方法1: 用马拉车算法（字符串动态规划）来求最长回文子串时间复杂度可以达到O(n).
可以参考这篇博客：https://www.cnblogs.com/grandyang/p/4475985.html，写的很好。
但是博客里面有个小失误：这个id应该不是最大回文字串中心的位置，而是所有的回文子串中，能延续到最右端的位置的那个回文子串的中心点位置，mx是回文串能延伸到的最右端的位置，这个应该没错，是id错了，两个没对应上。我一开始按照id是最大回文字串中心的位置来写了一段代码，也过了，后来发现根本不对，那样的话时间复杂度就达不到O(n),因为比如说一个特别特别长的字符串，一开始有一个最大回文子串，然后接下来的那些字符串匹配的时候就都用不上前面的匹配结果，都需要匹配很多次，时间复杂度就达不到O(n)了。resCenter是最大回文子串的中心位置才对。
#include#include #include #include using namespace std;string Manacher(string s){ //预处理，加"#" string t = "$#"; for (char x : s) { t += x; t += "#"; } vector p(t.size(), 0); int id = 0, mx = 0,i, resCenter=0, resLength=0; for (i = 1; i < t.size(); ++i) { p[i] = mx> i ? min(mx - i, p[2 * id - i]) : 1; while (t[i - p[i]] == t[i + p[i]]) ++p[i]; if (mx < p[i] + i) { mx = p[i] + i; id = i; } if (p[i] > resLength) { resCenter = i; resLength = p[i]; } } return s.substr((resCenter - resLength) / 2, resLength - 1);}int main(){ string s1 = "12212"; cout << Manacher(s1) << endl; string s2 = "122122"; cout << Manacher(s2) << endl; string s = "waabwswfd"; cout << Manacher(s) << endl; return 0;}
方法2:采用中心点扩散的方法，时间复杂度是O(n^2)。把字符之间加上'#'，避免分奇偶两种情况讨论。
class Solution {public: string longestPalindrome(string s) { string a="#", re, final_re; for(char x:s){ a=a+x+"#"; } for(int i=0; i =0 && q+1