$Manacher$算法

发表于 更新于 Changyan：

例题：回文串

$Manacher$算法，又叫“马拉车”算法，只适用于在时间复杂度为$O(N)$的情况下求解一个字符串的最长回文子串长度的问题。

一、预处理

回文串长度个数为奇数，则其对称位置在某个字符。否则在两个字符中间，非常不利于计算回文串长度。

处理方法： 在字符串两边加 ‘#’ ，任意两个字符串之间加 ‘#’。
字符串新长度 $=$ 原长度 $\times$ 2 $+$ 1；（’#’ 个数始终比原字符个数多 1）。这样的处理保证了任意字符串都是奇数字符串。如果知道回文字符串的半径就可以求出字符串长度，也就可以求出原字符串长度。

原字符串长度 $=$ （字符串长度 $-$ 1）$/$ 2 $=$ （r $\times$ 2 $-$ 1 $-$ 1）$/$ 2 $=$ r $-$ 1。（假设该字符串就是回文串，因此字符串长度 = r $\times$ 2 $-$ 1，因此规定一个字符的回文串半径为 1）

关于 字符串长度 $=$ r $\times$ 2 $-$ 1 有如下示意。

1
2
3
old_str: a b a
new_str: $ # a # b # a # ^
   r   : 0 1 2 1 4 1 2 1 0

二、算法过程

维护一个最靠右边的回文串 $(sl-sr)$，计算一个记录着以当前字符 $b[i]$ 为中心的回文串的半径 $p[i]$。每次计算有以下情形：

更新 $p[i]$ 时可以利用对称性:

1
2
//i 在 mr 的内部: p[i] = min(p[j], mr - i)   j为i的对称点  j = 2 * mid - i
if(i < mr) p[i] = min(p[mid * 2 - i], mr - i);

$p[i]$ 关于 最右回文串的对称字符串在 $(sl-sr)$ 范围内，那么 $p[i]$ = $p[j]$ ($j$ 为对称子串的中心)不在范围内，因为$(sl - sr)$ 是最右的回文串，所以 $p[i]$ 等于其对称子串在 $(sl-sr)$ 中的最大半径。（因为其对称子串范围超过了 $(sl-sr)$，且 $(sl-sr)$ 无法向右扩张，即 $str[sr + 1] != str[sl - 1]$。 那么此时 $p[i]$ 就等于其对称子串在$(sl-sr)$范围内的半径）

不可以利用对称性就暴力向外扩张的求 $p[i]$

1
2
3
4
5
p[i] = 1; 
// 每次暴力往两边扩展

// 重构字符串时有添加边界'$'和'^', 这里不需要判断是否越界
 while(b[i - p[i]] == b[i + p[i]]) p[i] ++;

计算结束后，用本次 p[i] 更新 最靠右的回文子串。

1
2
3
4
5
6
// 更新mr 和 mid
if(mr < i + p[i])
{
    mr = i + p[i];
    mid = i;
}

三、图解

249c680788f694a807ed4dde6dddd58.png

代码：

时间复杂度：$O(N)$

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 20000010;

int n;
char a[N], b[N];
int p[N];

// 变换原串, 使得原串中任何一个回文串对应到新串里都是一个长度为 奇数 的回文串
void init()
{
    int k = 0;
    b[k ++] = '$', b[k ++] = '#';
    for(int i = 0; i < n; i ++) b[k ++] = a[i], b[k ++] = '#';
    b[k ++] = '^';
    n = k;
}

void manacher()
{
    // mr为最靠右的回文串的右边界（开区间，mr为右边界的下一个点），mid为中点
    int mr = 0, mid = -1;
    for(int i = 1; i < n; i ++) 
    {
        //i 在 mr 的内部: p[i] = min(p[j], mr - i)   j为i的对称点  j = 2 * mid - i
        if(i < mr) p[i] = min(p[mid * 2 - i], mr - i); 
        // 否则 p[i] 从 1开始
        else p[i] = 1; 

        // 每次暴力往两边扩展
        while(b[i - p[i]] == b[i + p[i]]) p[i] ++; 
        
        // 更新mr 和 mid
        if(mr < i + p[i])
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main()
{
    scanf("%s", a);
    n = strlen(a);

    init();
    manacher();

    int res = 0;
    // 原串的回文串长度 对应 新串中的回文串半径（包括str[i]）减1
    for(int i = 1; i < n; i ++) res = max(res, p[i] - 1);
    printf("%d\n", res);

    return 0;
}