Manacher’sAlgorithm（神啊）

&＃xff08;转载自&＃xff09;http://blog.csdn.net/hopeztm/article/details/7932245

这里描述了一个叫Manacher’s Algorithm的算法。

算法首先将输入字符串S&＃xff0c; 转换成一个特殊字符串T&＃xff0c;转换的原则就是将S的开头结尾以及每两个相邻的字符之间加入一个特殊的字符&＃xff0c;例如#

例如: S &＃61; “abaaba”, T &＃61; “#a#b#a#a#b#a#”.

为了找到最长的回文字串&＃xff0c;例如我们当前考虑以Ti为回文串中间的元素&＃xff0c;如果要找到最长回文字串&＃xff0c;我们要从当前的Ti扩展使得 T_i-d … T_i&＃43;d 组成最长回文字串. 这里 d 其实和 以Ti为中心的回文串长度是一样的. 进一步解释就是说&＃xff0c;因为我们这里插入了 # 符号&＃xff0c;对于一个长度为偶数的回文串&＃xff0c;他应该是以#做为中心的&＃xff0c;然后向两边扩&＃xff0c;对于长度是奇数的回文串&＃xff0c;它应该是以一个普通字符作为中心的。通过使用#&＃xff0c;我们将无论是奇数还是偶数的回文串&＃xff0c;都变成了一个以Ti为中心&＃xff0c;d为半径两个方向扩展的问题。并且d就是回文串的长度。

例如 #a#b#a#, P &＃61; 0103010, 对于b而言P的值是3&＃xff0c;是最左边的#&＃xff0c;也是延伸的最左边。这个值和当前的回文串是一致的。

如果我们求出所有的P值&＃xff0c;那么显然我们要的回文串&＃xff0c;就是以最大P值为中心的回文串。

T &＃61; # a # b # a # a # b # a #
P &＃61; 0 1 0 3 0 1 6 1 0 3 0 1 0

例如上面的例子&＃xff0c;最长回文是 “abaaba”, P₆ &＃61; 6.

根据观察发现&＃xff0c;如果我们在一个位置例如 abaaba的中间位置&＃xff0c;用一个竖线分开&＃xff0c;两侧的P值是对称的。当然这个性质不是在任何时候都会成立&＃xff0c;接下来就是分析如何利用这个性质&＃xff0c;使得我们可以少算很多P的值。

下面的例子 S &＃61; “babcbabcbaccba” 存在更多的折叠回文字串。

C表示当前的回文中心&＃xff0c;L和R处的线表示以C为中心可以到达的最左和最右位置&＃xff0c;如果知道这些&＃xff0c;我们如何可以更好的计算C后面的P[i]. 

假设我们当前计算的是 i &＃61; 13, 根据对称性&＃xff0c;我们知道对称的那个下标 i&＃39; &＃61; 9. 

根据C对称的原则&＃xff0c;我们很容易得到如下数据P[ 12 ] &＃61; P[ 10 ] &＃61; 0, P[ 13 ] &＃61; P[ 9 ] &＃61; 1, P[ 14 ] &＃61; P[ 8 ] &＃61; 0).

Now we are at index i &＃61; 15, and its mirrored index around C is i’ &＃61; 7. Is P[ 15 ] &＃61; P[ 7 ] &＃61; 7?

当时当i &＃61; 15的时候&＃xff0c;却只能得到回文 “a#b#c#b#a”, 长度是5&＃xff0c; 而对称 i &＃39; &＃61; 7 的长度是7. 

如上图所示&＃xff0c;如果以 i, i&＃39; 为中心&＃xff0c;画出对称的区域如图&＃xff0c;其中以i‘ &＃61; 7 对称的区域是 实心绿色 &＃43; 虚绿色 和 左侧&＃xff0c;虚绿色表示当前的对称长度已经超过之前的对称中心C。而之前的P对称性质成立的原因是 i 右侧剩余的长度 R - i 正好比 以 i‘ 为中心的回文小。 

扩充P[i] 之后&＃xff0c;我们还要做一件事情是更新 R 和 C&＃xff0c; 如果当前对称中心的最右延伸大于R&＃xff0c;我们就更新C和R。在迭代的过程中&＃xff0c;我们试探i的时候&＃xff0c;如果P[i&＃39;] <&＃61; R - i, 那么只要做一件事情。 如果不成立我们对当前P[i] 做扩展&＃xff0c;因为最大长度是n&＃xff0c;扩展最多就做n次&＃xff0c;所以最多做2*n。 所以最后算法复杂度是 O(n)