本文在这篇文章的基础上完成。下面说下Mancher算法。

一、Mancher可以解决的问题

看这里，题目的核心意思是求指定字符串的最长回文(自行百度什么是“回文”)子字符串的长度。传统做法我们这里就不讲了，直接讲Macher。

1、字符串转换

回文字符串长度可是奇数，也可是偶数。为了方便处理，我们通过在每个字符之间以及字符首位加特殊符号的方式来统一奇偶问题。举个例子：

S=“abba”，变为T="#a#b#b#a#" 。我们会发现S的长度是4，而T的长度为9，长度变为奇数了。

那S的长度为奇数的情况时，变化后的长度还是奇数吗？

再举个例子：

S=“abcba”，变化为T=“#a#b#c#b#a#”，T的长度为11。

所以我们发现其改造的目的是将字符串的长度变为奇数，这样就可以统一的处理奇偶的情况了。

2、计算新字符串的回文半径

• 创建数组P,P[i]表示以T[i]为中心的回文半径。举个例子

图一

数组P有这样的性质,P[i] - 1 = 原字符串中，以当前i点元素为中心的回文字符串的长度。证明过程如下：

在字符串T中，以i点为中心的回文长度为:2p[i]-1,p[i]为半径。

假设，该回文字符串的中'#'为y个，非'#'为x个，那么：

x + y = 2P[i] - 1;

通过图(1)可知,该回文中'#'一定比非'#'多一个，即：

y -x = 1;

解以上两个方程得:

y = P[i]

x = P[i] - 1

• 如何求数组P？

先上一张图：

                                                                        图二

假设，当前最长回文的边界为[L,R]，Mi为中心，求P[i]的值。毫无疑问，现在i点以前的元素都值都计算过了，根据回文的特性，i点关于Mi的对称点j的值p[j]，而且，P[i] = P[j]。根据对称关系，i-Mi = Mi - j得到j = 2Mi - i。

当 i < R时

如果，P[i] < R - i，说明以元素i为中心的回文长度一定在区间(R,L)内。

如果，P[i] >= R - i,说明以第i个字符为中心的回文半径可能已经超出R了，至于是否超出，要看第(R+1)个字符关于点i是否对称。

当 i >= R时，只能做以i为中心的字符对称匹配。

下面上一段js代码：

function regular_str(s){
    var res="$#";
    for(var i=0;i<s.length;++i)
    {
        res+=s[i];
        res+="#";
    }
    return res;
}
function mancher(str){
	str = regular_str(str);
	var R = 0,mi = 0,max_length = 0;
	var p = [];
	for(var i=0;i < str.length;i++){
		p[i] = Math.min(i<R?Math.min(p[2*mi-i],R-i):1);
		/**
		  Math.min(p[2*mi-i],R-i)仔细解释下
		  这里为什么选两者中小的呢？
		  当p[2*mi-i]较小时，说明以i点处字符为中心的回文在(R,L)区间内，直接附值即可。
		  当p[2*mi-i]较大时，说明，以i点处字符为中心的回文至少在区间[R,L]内，所以先附值(R-i),然后再一一做对称匹配。


		**/
		while(str.charAt([i+p[i]]) == str.charAt(i-p[i])){ //做对称匹配
		  p[i] = p[i]+1;
		}
		if(R < p[i]+i-1){ //中心+半径-重复位置
		   R = p[i]+i-1;
		   mi = i;
		}
		if(max_length < p[i]){	
		   max_length = p[i];
		}
	}
	return max_length-1;
}