简介
Manacher’s Algorithm是用来查找一个字符串的最长回文子串的线性方法，由一个叫Manacher的人在1975年发明的。中文谐音“马拉车”算法。时间复杂度O(|S|)。
朴素算法
给出一个朴素的中心扩展算法，寻找最长回文子串，枚举所有奇偶回文中心点（n+n-1个），然后向两端扩展，判断左右字符是否相等即可。时间复杂度$ O(|S|^{2}) $。
实现代码如下：
1int expand(char* s, int n, int l, int r)
2{
3 while(l>=0 && r<=n && s[l]==s[r])
4 l--, r++;
5 return r-l-1;
6}
7
8int simple(char* s)
9{
10 int n = strlen(s), len = 0;
11 int start = 0, end = 0;
12
13 for(int i=0; i<n; i++)
14 {
15 int t = max(expand(s, n, i, i), expand(s, n, i, i+1));
16 if(t > len){
17 len = t;
18 start = i - (len - 1) / 2;
19 end = i + len / 2;
20 }
21 }
22 for(int i=start; i<=end; i++){
23 printf("%c", s[i]);
24 }
25 printf("\n");
26 return len;
27}
预处理
首先我们处理一下长度的奇偶，在每个字符间插入'#'，并且为使得扩展到边界能自动结束，在首尾分别插入'^'和'$'（不会在原串中出现的字符）。这样字符串的长度就被处理为奇数了。
预处理代码如下：
1int manacher_init(char *s, char *t, int n)
2{
3 int j = 2; t[0] = '$', t[1] = '#';
4 for (int i=0; i<n; i++)
5 {
6 t[j++] = s[i];
7 t[j++] = '#';
8 }
9 t[j] = '\0';
10 return j;
11}
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种情况：
(1) 当i$<$mx时，令j=2*id-i，即i关于id的对称点，如果i+p[j]$<$mx，那么由回文串的性质可知p[i]=p[j]。
(2) 当i$<$mx时，令j=2*id-i，即i关于id的对称点，如果i+p[j]$>=$mx，那么可以确定的是p[i]=mx-i，然后超出部分就需要中心拓展比较了。
(3) 当i>=mx时，无法根据已知条件判断，只能中心拓展比较了。
按照以上思路，遍历一下即可，注意更新id和mx。此写法得出的p[i]是最长半径数组，并非最长回文子串长度，ans需要减1，若有需要，修改中心扩展代码即可。代码如下：
1int manacher(char *t, int *p, int n)
2{
3 int id = 0, mx = 0, ans = 0;
4 for (int i=1; i<=n; i++)
5 {
6 p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;
7
8 while (t[i+p[i]] == t[i-p[i]]) p[i]++; // 中心扩展
9
10 if (mx < i+p[i])
11 mx = i+p[i], id = i;
12
13 ans = max(ans, p[i]);
14 }
15 return ans-1;
16}
模板
1char s[mxn], t[mxn];
2int p[mxn];
3
4int manacher_init(char *s, char *t, int n)
5{
6 int j = 2; t[0] = '$', t[1] = '#';
7 for (int i=0; i<n; i++)
8 {
9 t[j++] = s[i];
10 t[j++] = '#';
11 }
12 t[j] = '\0';
13 return j;
14}
15
16int manacher(char *t, int *p, int n)
17{
18 int id = 0, mx = 0, ans = 0;
19 for (int i=1; i<=n; i++)
20 {
21 p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;
22
23 while (t[i+p[i]] == t[i-p[i]]) p[i]++; // 中心扩展
24
25 if (mx < i+p[i])
26 mx = i+p[i], id = i;
27
28 ans = max(ans, p[i]);
29 }
30 return ans-1;
31}
32
33int expand(char* s, int n, int l, int r)
34{
35 while(l>=0 && r<=n && s[l]==s[r])
36 l--, r++;
37 return r-l-1;
38}
39
40int simple(char* s)
41{
42 int n = strlen(s), len = 0;
43 int start = 0, end = 0;
44
45 for(int i=0; i<n; i++)
46 {
47 int t = max(expand(s, n, i, i), expand(s, n, i, i+1));
48 if(t > len){
49 len = t;
50 start = i - (len - 1) / 2;
51 end = i + len / 2;
52 }
53 }
54 // for(int i=start; i<=end; i++){
55 // printf("%c", s[i]);
56 // }
57 // printf("\n");
58 return len;
59}
60
61int main()
62{
63 scanf("%s", s);
64 int n = manacher_init(s, t, strlen(s));
65 printf("%d\n", simple(s));
66 printf("%d\n", manacher(t, p, n));
67 for(int i=0; i<n; i++){
68 printf("%d ", p[i]);
69 }
70 printf("\n");
71 return 0;
72}