转载

求最长回文子串 - leetcode 5. Longest Palindromic Substring

ps：纯原创讲解算法实现也要移除首页？

写在前面:忍不住吐槽几句今天上海的天气，次奥，鞋子里都能养鱼了...裤子也全湿了，衣服也全湿了，关键是这天气还打空调，只能瑟瑟发抖祈祷不要感冒了....

前后切了一百零几道 leetcode 的题(solution同步在 github ），主要是拣难度系数定为easy的水题做...好吧，这是第一道算法题。不知哪位大神说的，所有的语言都会过时，只有数据结构和算法才是永恒。

今天要重点讲的是优雅的 Manacher算法 ，先来看这道题 Longest Palindromic Substring ，题目很简单，给你一个字符串，找到最长的回文子串。啥叫回文串？就是前后看都一样的串，比如 abcba ， abba ，因为题目给的数据量不大（1000），所以可以枚举字符串的每个位置当做回文对称点，回文对称点是我给它的一个概念，比如 abcba 的回文对称点就是idx=2也就是c的位置。But！并不是每个回文串都有对称点，比如 abba ，只有对称轴，它就没有点！怎么办？机智的coder想出了一个简单的用空间换取代码实现复杂度的方法，这也是Manacher算法的第一步：

abcba -> #a#b#c#b#a# abba  -> #a#b#b#a#

这么一来，每个回文串就都有回文对称点了（可能是字母，也可能是#）。之后我们就能枚举对称点，然后向两边扩散开去，比较字符是否一样。为了不用判断是否已经到了边界，我们最初在字符串的开头再加个字符 * ，只要该字符和 # 以及字符串里其他字符都不一致即可。这样是可以AC的，虽然复杂度达到了O(n^2)。接下去我们介绍复杂度为O(n)的Manacher算法。

我们试着以字符串 babcbade 举例，首先把字符串像上面一样变形：

babcbade -> *#b#a#b#c#b#a#d#e#

然后我们设置一个dp数组， dp[i]表示以变形后第i个元素为对称点的最长回文子串的半径，同样以上面的字符串举例，可以得到dp数组：

*#b#a#b#c#b#a#d#e# 112121216121212121

我们可以很容易地发现， 要求的最长回文子串的长度即dp数组最大值减去1 。于是如何快速地求得该数组成为关键。假设我们已经得到了dp[6]的值，dp[10]的初始值也不难确定，因为它们两个元素根据idx=8对称（#a#b#c#b#a#)，所以可以不用从1开始向两边扩散了。

我们用 maxn 维护当前存在的回文子串能达到最右的位置+1（maxn位置不可达到），用 idx 维护当前能到达最右+1的回文子串的回文中心点位置，实现该dp数组求值的核心代码如下：

for (var i = 1, len = str.length; i < len; i++) {   if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);   else dp[i] = 1;    while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;    if (dp[i] + i > maxn)     maxn = dp[i] + i, idx = i; }

完整的AC代码：

// return the Longest Palindromic Substring of s function Manacher(s) {   var str = '*#'     , dp = []     , maxn = 0     , idx = 0;    for (var i = 0, len = s.length; i < len; i++)     str += s[i] + '#';    for (var i = 1, len = str.length; i < len; i++) {     if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);     else dp[i] = 1;      while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;      if (dp[i] + i > maxn)       maxn = dp[i] + i, idx = i;   }    var ans = 0     , pos;    for (var i = 1; i < len; i++) {     if (dp[i] > ans)       ans = dp[i], pos = i;   }    var f = str[pos] === '#'     , tmp = f ? '' : str[pos]     , startPos = f ? pos + 1 : pos + 2     , endPos = f ? dp[pos] - 3 + startPos : dp[pos] - 4 + startPos;    for (var i = startPos; i <= endPos; i += 2)      tmp = str[i] + tmp + str[i];    return tmp; }  var longestPalindrome = function(s) {   var str = Manacher(s);   return str; };

正文到此结束