Manacher算法,

又叫“马拉车”算法,

可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

字符串算法之Manacher

之前一直都在不知所云地套板子。

直到今天,下定决心,要搞懂Manacher的原理。

然后,原来不过如此嘛XD

从最简单的判断回文的方法说起。

即拉出字符串中的每个子串,判断它们是否回文。

拉出子串需要O(n^2),判断是否回文需要O(n),所以这种方法的时间复杂度是O(n^3)。

那么再精巧一点,我们可以从字符串中的每个字符下手,对于每个字符向两边扩展求回文长度。这样子,时间复杂度降到了O(n^2)。

我们是否可以找到一种O(n)的算法呢?答案是肯定的。

不考虑dp的方法,其实我们能从回文串本身得到一些启示。

例如:

c a b a d a b a b

我们运用第二种方法对每个字符进行分析。

从第二位a开始,b≠c,因此f[2]=1;

第三位b,c a b a d a b a b,因此,f[3]=3;

第四位a,b≠d,f[4]=1;

第五位d,c a b a d a b a b,因此,f[5]=7;

下面!!!高能!!!

第六位a,b≠d,f[6]=1。但是!是不是觉得似曾相识?对!由于回文串具有对称性质,所以事实上,因为第四位构不成回文串,所以与此对应的第六位也是不可能有的。

第七位b,同理,第七位等同于第三位,f[7]=f[3]=3;

第八位a,是不是要脱口而出f[8]=f[2]=1?等等!我们发现 c a b a d a b a b ,因此,f[8]=3。这是为什么呢?由于s[1]≠s[9],所以f[8]和f[2]是不一定相等的。

这样一个分析过程,实际上就是Manacher算法所需要做的。

  1. 首先,我们要记录下目前已知的回文串能够覆盖到的最右边的地方

  2. 同时,覆盖到最右边的回文串所对应的回文中心也要记录

  3. 以每一位为中心的回文串的长度也要记录,后面进行推断的时候能用到

  4. 对于新的中心,我们判断它是否在右边界内,若在,就计算它相对右边界回文中心的对称位置,从而得到一些信息,同时,如果该中心需要进行扩展,则继续扩展就行。

但是这样会出现一些问题,比如回文长度为偶数的时候,不存在严格意义上的回文中心。所以我们需要对字符串先进行一波预处理。

  1. 先对字符串进行预处理,两个字符之间加上特殊符号#

  2. 然后遍历整个字符串,用一个数组来记录以该字符为中心的回文长度,为了方便计算右边界,我在数组中记录长度的一半(向下取整)

  3. 每一次遍历的时候,如果该字符在已知回文串最右边界的覆盖下,那么就计算其相对最右边界回文串中心对称的位置,得出已知回文串的长度

  4. 判断该长度和右边界,如果达到了右边界,那么需要进行中心扩展探索。当然,如果第3步该字符没有在最右边界的“羽翼”下,则直接进行中心扩展探索。进行中心扩展探索的时候,同时又更新右边界

  5. 最后得到最长回文之后,去掉其中的特殊符号即可

下面放上我觉得比较完美的一个板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 2e5 + 10;
char s[maxn], sNew[maxn<<1];
int p[maxn<<1], id, mx=0;
int L, R; //回文串在原串的左右端点位置

int Init()
{
int len = strlen(s);
sNew[0] = '$';
sNew[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
sNew[j++] = s[i];
sNew[j++] = '#';
}
sNew[j] = '\0';
return j;
}

int Manacher()
{
int len = Init();
int max_len = -1;
mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx) p[i] = min(p[2 * id - i], mx - i);
else p[i] = 1;

while (sNew[i - p[i]] == sNew[i + p[i]]) p[i]++;

if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}

if(max_len < p[i])
{
max_len = p[i];
L = (i - p[i])>>1;
R = (i + p[i] - 4)>>1; ///R = (i + p[i])/2 -2;
}

}
return max_len;
}

最后更新: 2019年08月07日 10:51

原始链接: http://yisin.top/2019/08/07/字符串算法之Manacher/

× 请我吃糖~
打赏二维码