Manacher Algorithm 马拉车算法

有一道比较经典的算法考题。

如何找出一串字符串中最长的回文子串呢？

例：babad中最长回文子串便是bab和aba。

解决这个问题的最直接的想法当然是暴力穷举了。

但很不幸，这种方法的时间复杂度为O(n^2)。

接下来容易想到的动态规划，时间复杂度居然差不多。。。。。

难道没有更好的方法了吗？？？？

有，这便是特别有趣巧妙Manacher's算法。

它的时间复杂度只有O(n)！！！！

首先我们来干件有趣的事：如果向原有字符串前后加上相同的字符

如#：b a b a d ——> # b # a # b # a #

下标 1 2 3 4 5 ——> 1 2 3 4 5 6 7 8 9

半径 1 2 3 2 1 ——> 1 2 3 4 5 4 1 2 1

新字符串的所有回文子串长度将是奇数，这样回文子串都有个中心。

新回文子串的半径-1=原回文子串的长度。

如：#b#a#b#半径为4，原子串bab的长度为3。

新回文子串的中心位置/2=原回文子串的位置。

（出现.5的情况，对应原子串长度为偶数，中心在字符之间）

尝试找最长子串时，最费时间的一步是什么？

找到某个字符为中心的回文串最大长度。

Manacher算法的精彩之处就在这里：运用一个规律

包含在回文串中的每个回文子串的最大长度以回文串的中心左右对称。

如：# b # a # b #

1 3 1 7 1 3 1

(此为以相应字符为中心的最长回文子串长度)

推广一下，若扩充后的字符串：

有一较长的回文子串，中心位置id，半径为r，起点id-(r-1),终点id+(r-1)。

若要找出id+i(i

若以id-i为中心的回文子串起点比id中心的子串起点靠后（完全包含）,则id+i为中心的最长回文子串与id-i的相同。

不完全包含意味着，以id+i为中心子串包含在id中的部分不需比较，只需直接比较接下来不包含的部分。

具体编程时，

先构建数组Rad[i]——记录以i为中心的回文子串的最大长度。

引入辅助变量mx——当前已经处理的回文子串所达最靠后的终点，

引入辅助变量id——终点最靠后的回文子串的中心字符下标。

对扩充完的字符串从左到右一一处理，若寻找i为中心的最长回文子串：

若mx

若mx>i，即其被包含前面某个回文子串里。即可使用上述规律：首先找出与i对称的下标j=id-(i-id)=2*id-1，得判断是否完全包含，如果j-Rad[j]>id-Rad[id]——完全包含，Rad[i]=Rad[j];

若不完全，明显以i下标字符为中心的回文长度不小于id+Rad[id]-i(即包含在id为中心回文子串的部分本身便是回文子串)，进一步向两侧对比，得到最后的Rad[i]。

得到Rad[i]后，若i+Rad[i]-1>mx——出现终点更靠后的回文子串，更新mx=i+Rad[i]-1，id=i。

最后找到最大半径Rad_max,得到对应的中心位置i_max。通过对应关系，求出原字符串的最长回文子串。

Manacher算法堪称效率最高的求回文子串的算法。