2018年6月10日
Manacher算法原理与实现
概述
Manacher算法是一种用于快速计算字符串中回文串长的算法,复杂度为O(n)。下面介绍该算法的原理及实现细节。
原理
我们从朴素地查找回文串开始,我们枚举回文串的回文中心,并向两边扩展,这种算法是O(n^2)的。我们来想一个问题,如果有串abcbaabcbaabcbaabcba
,它本身是回文的,而子串abcba
也是回文的,在寻找过程中,abcba
可能会被多次遍历到。我们能否把已经找到过的abcba
信息利用起来,优化算法呢。Manacher就实现了这种优化。
首先我们要对字符串进行一步处理,因为奇回文abcba
和偶回文abba
存在不同的模式,需要分别考虑,我们把字符之间都插入一个特殊字符,如#
,就可以把偶回文也转化为奇回文的情况了,如abba
→$#a#b#b#a#
。其中,字符串0位置的字符$
是用来防止越界的。
这里给一个对齐表方便观察。
我们考虑在上面的例子中,#a#b#c#b#a#a#b#c#b#a#
存在子回文串#a#b#c#b#a#
,在下一次遇到该回文串的回文中心时,我们可以考虑在整个大回文串找到这个中心的对称点,就像这样:
#a#b#c#b#a#a#b#c#b#a# ^ ^
并把对称点的答案直接拿过来用。如果我们用mx代表当前极大回文串右端点,id代表当前极大回文串中心位置,p数组代表某个位置为中心的最长回文串半径,那么代码写出来应该是这样的:
if(i < mx) p[i] = std::min(p[2 * id - i], mx - i);
然后我们再来扩展修正这个p值,动态地维护当前极大回文串即可。
在处理过的串中p数组代表的半径,而我们发现p数组的值实际上为原串中该位置为中心的最长回文串长+1,因此可以这样直接计算出答案。
实现
本代码可以通过【P3805】【模板】manacher算法 – 洛谷一题。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int MAXN = 22000005;
char s1[MAXN], s2[MAXN];
int n, tot, p[MAXN], mx;
inline int manacher() {
s2[tot++] = '$'; s2[tot++] = '#';
for(int i = 1; i <= n; i++) {
s2[tot++] = s1[i]; s2[tot++] = '#';
}
int mxlen = 0, mx = 0, id;
for(int i = 1; i < tot; i++) {
if(i < mx) p[i] = std::min(p[(id << 1) - i], mx - i);
else p[i] = 1;
while(s2[i - p[i]] == s2[i + p[i]]) p[i]++;
if(mx < i + p[i]) {
id = i; mx = i + p[i];
}
mxlen = std::max(mxlen, p[i] - 1);
}
return mxlen;
}
int main() {
scanf("%s", s1 + 1); n = strlen(s1 + 1);
printf("%d", manacher());
return 0;
}