【专题】Manacher
简介
Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的。中文谐音“马拉车”算法。时间复杂度O(|S|)。
朴素算法
给出一个朴素的中心扩展算法,寻找最长回文子串,枚举所有奇偶回文中心点(n+n-1个),然后向两端扩展,判断左右字符是否相等即可。时间复杂度$ O(|S|^{2}) $。

实现代码如下:
1 | int expand(char* s, int n, int l, int r) |
预处理
首先我们处理一下长度的奇偶,在每个字符间插入'#'
,并且为使得扩展到边界能自动结束,在首尾分别插入'^'
和'$'
(不会在原串中出现的字符)。这样字符串的长度就被处理为奇数了。

预处理代码如下:
1 | int manacher_init(char *s, char *t, int n) |
Manacher算法
idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T | $ | # | a | # | b | # | a | # | b | # | a | # | a | # | b | # | c | # | \0 |
r | 1 | 2 | 1 | 4 | 1 | 6 | 1 | 4 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 2 | 1 | ||
p | 0 | 1 | 0 | 3 | 0 | 5 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 |
观察可得,最长回文子串p[i] = 最长回文半径r[i] - 1,p[i]所代表的子串在原串的起点为(i-p[i])/2。
那么p[i]怎么求呢,令mx为当前已求出的最右的回文子串右边界,令id为这个回文子串的中心点,讨论以下3种情况:
- 当i\(<\)mx时,令j=2*id-1,即i关于id的对称点,如果i+p[j]\(<\)mx,那么由回文串的性质可知p[i]=p[j]。

- 当i\(<\)mx时,令j=2*id-1,即i关于id的对称点,如果i+p[j]\(>=\)mx,那么可以确定的是p[i]=mx-i,然后超出部分就需要中心拓展比较了。

- 当i>=mx时,无法根据已知条件判断,只能中心拓展比较了。

按照以上思路,遍历一下即可,注意更新id和mx。此写法得出的p[i]是最长半径数组,并非最长回文子串长度,ans需要减1,若有需要,修改中心扩展代码即可。代码如下:
1 | int manacher(char *t, int *p, int n) |
模板
1 | char s[mxn], t[mxn]; |