本文共 3578 字，大约阅读时间需要 11 分钟。
题目链接：
题意：找最长回文子串(注意不是回文序列，不一样，字串需要连续，序列不需要连续)
方法一：
这一题说实话，只想到最“土”的方法，就是找到所有的可能的串，然后得到最长的回文串。
需要注意：回文串有奇数和偶数之分，所以以当前这个点为中心，存在两种：这个点是最中间的点；这个点和之前一个点需要进行比较。
看代码如下：
class Solution {public: string longestPalindrome(string s) { int max_len = 0, n = s.length(), len = 0, i, start = 0; int low, high; // 当前点参与回文比较 // for (i = 0; i < n; ++i){ low = i - 1; high = i; len = 0; while (low >= 0 && high < n && s[low] == s[high]){ --low; ++high; len += 2; } if (max_len < len){ start = low + 1; max_len = len; } } // 当前点不参与比较 // for (i = 0; i < n; ++i){ low = i - 1; high = i + 1; len = 1; while (low >= 0 && high < n && s[low] == s[high]){ --low; ++high; len += 2; } if (max_len < len){ start = low + 1; max_len = len; } } return s.substr(start, max_len); }}; 方法二：（网上学习得到） 这一题还有一个很有“技术”的算法，这个真的挺不错的！号称Manacher’s Algorithm，时间复杂度是O(n)。
1、首先这个算法建立在“奇数”数量字符字符串中才好使，所以第一步我们需要将原始的字符串改造成奇数个数，方法是，在所有字符之间个收尾都插入一个#字符，那么原来奇数的还是奇数，原来偶数的也是奇数个数了，例如：
aabb ==> #a#a#b#b#
aba ===> #a#b#a#
2、然后我们需要一个数组P记录以i字符为中心，向两边扩展最长的回文串。这个算法的优势在于什么呢？其实就是减少了一些位置处的回文串的计算。他借助的是回文串的对称性。例如：现在有一个回文串：
a b a b a b a b a
1 3 5 1 9 1 ？
根据前面的位置计算我们知道现在这个串是一个回文串，现在遍历到？位置，那么我们需要计算以？为中心(即a)的最长回文字符串是多少，一般情况我们是从？向左和向右进行遍历处理。但是存在一种情况是，如果前面(本例中中就是中间的a)是一个很大的回文字符串，？在这个串内，那么这个？可以不用计算就能得到结果，因为是和左边自己对称的a的值是一样的即5！所以不用遍历就知道答案是5！
a b a b a b a b a
所以这个算法其实就是钻了这个空子~~~
最终我们呢找到P数组中最大的值，就是所谓的以i为中心能扩张最大的回文串就是我们需要的结果。
下面具体说说本算法：
对于下面例子：
T = # a # b # a # a # b # a # P = 0 1 0 3 0 1 6 1 0 3 0 1 0
首先我们呢需要知道，以最大值6为中心，这个值其实就是最大回文串长度，因为加入了相等长度的#，那么其实12/2=6就是咯~
那么P到底是怎么计算的呢？
我们看一个字符串：S = “babcbabcbaccba”.
如果现在我们遍历了的情况是下图：
（图片来自互联网）
C代表的是现在的中心点，L和R分别是以这个点为中心点扩展到两边最远的长度边界！
现在我们需要知道？处是什么答案，我们根据上面的理解，显然是以C为中心和？对称位置的值即9号位置，所以？=1。同理我们知道后面的# 和c处也是和前面一样对称的值！但是到了i=15处！！！有什么问题，看看：
（图片来自互联网）
可以知道对称位置7处，值是7，意思是以7为中心可以向两边扩展长度7。但是我们知道15处，不能扩展到7，只能扩展到5就结束了！这个是个关键处理！原因是什么呢？是由于i=15位置处如果想达到扩展7，必须要超过右边界R！！！而R之外的情况我们当前还是未知的！所以没有办法直接赋值对称位置较大的值7！现在只能赋值5！如果想扩展到7，只有向外扩展R，然后和左边进行比较！所以
P[i] = min(R-i, P[i对称值])
同时需要注意，如果R被扩展了，那么就需要更新，同时中心点C也被更新咯！
3、那么现在总结一下这个算法的步骤：
1)、如果当前位置在之前的那个中心范围内，即如果i<R，那么就可以使用对称性做，P[i] = min(R-i, P[对称值]);如果不在这个范围内，那么就是0为初值！！！
2)、然后看看能不能向当前已有的范围P[i]外面扩展，如果可以，那么++P[i]
3)、最后需要判断当前i为中心的右边界是不是已经超越之前的边界了，如果是，则需要更新右边界R和中心点C。
4)、最后，找到最大的P[i]就OK！
下面看代码：
class Solution {public: string longestPalindrome(string s) { // 首先我们处理s字符串 // string str = "^"; int i = 0, n = s.length(); while (i < n) { str += "#"; str += s[i++]; } // 结尾 // str += "#$"; // 下面正式处理 // n = str.length(); int *P = (int *)malloc(n*sizeof(int)); memset(P, 0, n*sizeof(int)); int C = 0, R = 0; for (i = 1; i < n - 1; ++i) { // 第一步，看看能不能取对称位置值 // 对称位置：C-(i-C)=2-i // int symmetry_i = 2*C - i; // 看看i在不在当前中心的回文范围内！ // 如果在那么取min(R-i, P[symmetry_i])， // 否则初始化为0 // P[i] = R > i ? min(R-i, P[symmetry_i]) : 0; // 下面看看以i为中心，在P[i]之外还能不能扩展 // while (str[i + P[i] + 1] == str[i - P[i] - 1]) ++P[i]; // 最后看看扩展的范围是不是超过R边界了 // 如果超过了，需要处理C和R // if (P[i] + i > R){ R = P[i] + i; C = i; } } // 找到最大的P[i]值 // int idx = 0; int max_len = 0; for (i = 0; i < n; ++i) { if (P[i] > max_len){ idx = i; max_len = P[i]; } } // 返回这个找到的字符串，注意使用的是原始字符串s哦！ // return s.substr((idx - max_len - 1)/2, max_len); }};