【专题】Manacher

简介

Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的。中文谐音“马拉车”算法。时间复杂度O(|S|)。

朴素算法

给出一个朴素的中心扩展算法,寻找最长回文子串,枚举所有奇偶回文中心点(n+n-1个),然后向两端扩展,判断左右字符是否相等即可。时间复杂度$ O(|S|^{2}) $。

暴力

实现代码如下:

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
int expand(char* s, int n, int l, int r)
{
while(l>=0 && r<=n && s[l]==s[r])
l--, r++;
return r-l-1;
}

int simple(char* s)
{
int n = strlen(s), len = 0;
int start = 0, end = 0;

for(int i=0; i<n; i++)
{
int t = max(expand(s, n, i, i), expand(s, n, i, i+1));
if(t > len){
len = t;
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
for(int i=start; i<=end; i++){
printf("%c", s[i]);
}
printf("\n");
return len;
}

预处理

首先我们处理一下长度的奇偶,在每个字符间插入'#',并且为使得扩展到边界能自动结束,在首尾分别插入'^''$'(不会在原串中出现的字符)。这样字符串的长度就被处理为奇数了。

init

预处理代码如下:

1
2
3
4
5
6
7
8
9
10
11
int manacher_init(char *s, char *t, int n)
{
int j = 2; t[0] = '$', t[1] = '#';
for (int i=0; i<n; i++)
{
t[j++] = s[i];
t[j++] = '#';
}
t[j] = '\0';
return j;
}

Manacher算法

idx0123456789101112131415161718
T$#a#b#a#b#a#a#b#c#\0
r12141614125212121
p01030503014101010

观察可得,最长回文子串p[i] = 最长回文半径r[i] - 1,p[i]所代表的子串在原串的起点为(i-p[i])/2。

那么p[i]怎么求呢,令mx为当前已求出的最右的回文子串右边界,令id为这个回文子串的中心点,讨论以下3种情况:

  1. 当i\(<\)mx时,令j=2*id-1,即i关于id的对称点,如果i+p[j]\(<\)mx,那么由回文串的性质可知p[i]=p[j]。
小于
  1. 当i\(<\)mx时,令j=2*id-1,即i关于id的对称点,如果i+p[j]\(>=\)mx,那么可以确定的是p[i]=mx-i,然后超出部分就需要中心拓展比较了。
大于
  1. 当i>=mx时,无法根据已知条件判断,只能中心拓展比较了。
超出

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int manacher(char *t, int *p, int n)
{
int id = 0, mx = 0, ans = 0;
for (int i=1; i<=n; i++)
{
p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;

while (t[i+p[i]] == t[i-p[i]]) p[i]++; // 中心扩展

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

ans = max(ans, p[i]);
}
return ans-1;
}

模板

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
char s[mxn], t[mxn];
int p[mxn];

int manacher_init(char *s, char *t, int n)
{
int j = 2; t[0] = '$', t[1] = '#';
for (int i=0; i<n; i++)
{
t[j++] = s[i];
t[j++] = '#';
}
t[j] = '\0';
return j;
}

int manacher(char *t, int *p, int n)
{
int id = 0, mx = 0, ans = 0;
for (int i=1; i<=n; i++)
{
p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;

while (t[i+p[i]] == t[i-p[i]]) p[i]++; // 中心扩展

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

ans = max(ans, p[i]);
}
return ans-1;
}

int expand(char* s, int n, int l, int r)
{
while(l>=0 && r<=n && s[l]==s[r])
l--, r++;
return r-l-1;
}

int simple(char* s)
{
int n = strlen(s), len = 0;
int start = 0, end = 0;

for(int i=0; i<n; i++)
{
int t = max(expand(s, n, i, i), expand(s, n, i, i+1));
if(t > len){
len = t;
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
// for(int i=start; i<=end; i++){
// printf("%c", s[i]);
// }
// printf("\n");
return len;
}

int main()
{
scanf("%s", s);
int n = manacher_init(s, t, strlen(s));
printf("%d\n", simple(s));
printf("%d\n", manacher(t, p, n));
for(int i=0; i<n; i++){
printf("%d ", p[i]);
}
printf("\n");
return 0;
}