【专题】Manacher

发表于 分类于 ， 本文字数： 787 阅读时长 ≈ 1 分钟
字符串专题，介绍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;
}