Manacher

简介

Manacher算法是一个时间复杂度为O（n）的最长回文子串的问题。俗称马拉车算法。

manacher是对对称轴算法的优化，对称轴算法是对字符串每个位置分别向左向右扩展，直到左右两边字符不同的时候，就得到这个位置的最长回文串。

回文串除了中间一个字符向两侧扩展之外，还有一种可能是偶数位的回文串中间两个字符是相同的，这种情况其实也是左右扩展，和奇数位的回文串是类似的。

对称轴算法的缺点如下：

需要根据回文串的奇偶性处理两种情况。

子串被重复访问。

原理

Manacher算法定义了几个概念。

Manacher本质上也是动态规划算法，假如每个位置i，i为中心的最长回文子串长度为p[i]，那么i+p[i]就是i为主心的回文串半径的右半径，那么在i到i+p[i]中的位置j的p[j]的值可以分为以下几类情况处理：

马拉车算法示意图

如果以位置i为对称轴，最长的回文串是cdcacbcbcacdc，即P[i]=13。P[i+1]的值可以根据如下方式获取，因为回文串的特性，以C为中心，在回文串的最大覆盖半径内，P[i+1]和P[i-1]两侧的字符串是完全相同的，P[i-1]在之前的流程中已经计算，所以P[i+1]=P[i-1]，同理，如果j1和j1‘对对称轴C是镜面对称的关系，那么P[j1]=P[j1']。

直到P[j2]的时候，情况发生了变化，j2+P[j2]已经到了最大半径的边缘，半径外侧是可能继续扩大回文串的边界的，比如这个case中，同理当p[j2']的回文串已经到了最左侧，同样需要继续判断。

每个位置i都有自己的回文半径，那么我们选择在计算位置j的时候选择哪个位置的回文半径作为基准计算呢，马拉车算法本质上通过之前的计算减少后续的计算，所以选择的位置i应该是其右侧半径最靠右的那个位置。