Manacher(马拉车)算法&模板

简介

Manacher算法可以在O(n)复杂度内解决一些回文串问题，例如求最长回文子串等。 该算法由Manacher发明。

思路

Manacher预处理部分

首先对于一个字符串，他的回文字串按长度可以分为偶数长度和奇数长度的回文子串，两种回文串的对称中心不同，这就可能会导致在处理时出现麻烦。 所以要对字符串进行处理，把奇偶子串进行统一。 比如：

ababa

Manaher的做法是插入一些无关字符(比如#)

#a#b#a#b#a#

这样的好处很明显，对于偶数子串它的对称中心就会变成#，这样就可以在处理后的字符串中找到原串中所有子串对应的对称中心了。

此外还需要在开始时加入另一个无关字符(比如$)

$#a#b#a#b#a#

那么此时预处理的部分就做完了

Manacher核心部分

Manacher最终的结果是得到了一个这样的数组p，P[i]表示以i为中心的回文串最多能向右延伸的长度. 比如:

$#a#b#a#b#a#(下标从1开始) p[2] = 1(#), p[3] = 2(a#), p[5] = 4(b#a#)

在得到p数组之前需要通过两个辅助变量idx和maxx分别表示距离当前最近的回文字串的范围 比如： 可以得到maxx = idx + p[idx]

假设已经处理出来了一段p，如果当前要求p的位置在maxx的范围之内的话就会有以下的关系。 $p[i]=min(p[idx\ast 2-i],maxx-i)$ 首先，如果在maxx之内的话，可以找到一个对称的$i^{\prime }$那么p[i’]已经求出，因为对称的关系，所以i’的p有一部分也是i的，可以很快求出$i^{\prime }=idx\ast 2-i$ 但是如果$p[i^{\prime }]$很大，超出了maxx的范围，那么此时超出的部分就不能保证$i$是对称的了，所以此时就需要设置一个上界$maxx-i$，就得到了$p[i]=min(p[idx\ast 2-i],maxx-i)$

如果i本身就不在maxx范围内那么直接暴力匹配就好了。

代码

char str[maxn], s[maxn]; int len1, len2, p[maxn]; void Manacher(){ str[1] = '$', str[2] = '#'; len2 = strlen(s + 1); for(int i = 1; i <= len2; i++){ str[i * 2 + 1] = s[i]; str[i * 2 + 2] = '#'; } len1 = len2 * 2 + 2; int idx = 0, maxx = 0; for(int i = 2; i <= len1; i++){ if(maxx > i)p[i] = min(p[idx * 2 - i], maxx - i);//核心代码 else p[i] = 1; for(; str[i + p[i]] == str[i - p[i]]; p[i]++);//暴力向后匹配 if(p[i] + i > maxx)idx = i, maxx = p[i] + i;//更新maxx和idx } }

最后得到的p的值减一就是该位置为中心最长回文串的长度了