今天学习一下新的字符串算法——manacher算法。

manacher简介

最长回文子串（英语：Longest palindromic substring）是计算机科学中的问题，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字符串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。

Manacher于1975年发现了一种线性时间算法[1]，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil [2]发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994)[3], Gusfield (1997)[4]发现了基于后缀树的算法。也存在已知的高效并行算法。(from wiki)

manacher实现

实现起来的话，其实我个人认为是比较简单的。首先防止奇偶序列的问题，我们在所有的字符之间以及末尾添加#让它变成奇数，再在首尾分别添加$和~作为截至判断的区分。

我将变量做如下定义：

  • \(s\) ：所求字符串
  • \(p[i]\) ：代表以字符 \(s[i]\) 为中心的最长回文半径。即满足在 \(0\le j\le p[i]\) 的条件下 \(s[i+j]==s[i-j]\) 永远成立。
  • \(wx\) ：目前所求的最远回文半径延伸的地方。即当前情况下的 \(\max(i+p[i])\)。
  • \(idx\) ：代表之前所求最远回文半径的中心。即取得wx时的 \(i\) 的值。

那么有了这个定义之后我们主要就是求这个p数组了，怎么求呢？

首先，如果我所在的位置在之前一个大的回文半径当中，那么我可以直接参考之前对称的那个位置上的p的值，比如下面这个例子。

1
2
3
a a a a b a a a a...
    ↑   ↑   ↑   ↑
    j idx   i   wx

这种情况下，我们不难发现，\(p[i]\) 至少是大于等于 \(p[j]\) 的，如果省略号后面马上跟一个 \(b\) 的话，那么它的 \(p\) 的值可能会涨，但是我们就不用判断它周围两边相不相等了啊。如果多了，那么我比较的次数就更少了。但是呢，其实可以发现，我们管的范围只能到wx，多余wx我们肯定不敢保证数据完全对称可用，所以这里我们限制一下 \(p[i]\) 最大可赋值为 \(wx-i\) 即可。

所以我们的核心代码就是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=1;i<len2;i++){
    if(mx>i){
        p[i]=min(p[2*idx-i],mx-i);
    }
    else{
            p[i]=1;
    }
    while(new_s[i+p[i]]==new_s[i-p[i]]){//继续扩展看看有没有可能
        p[i]++;
    }
    if(i+p[i]>mx){    
        mx=i+p[i];
        idx=i;
    }
}

标程

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
#include<bits/stdc++.h>
#define maxn 22000005
using namespace std;
char new_s[maxn];
char s[maxn<<1];
int p[maxn];
int main(){
    //freopen("2.in","r",stdin);
    scanf("%s",s);
    new_s[0]='$';
    new_s[1]='#';
    int len1=strlen(s),len2;
    for(int i=0;i<len1;i++){
        new_s[2*i+3]='#';
        new_s[2*i+2]=s[i];
    }
    len2=strlen(new_s)+1;
    new_s[len2-1]='~';
    
    int mx=0,idx=0,j=0;
    
    for(int i=1;i<len2;i++){
        if(mx>i){
            p[i]=min(p[2*idx-i],mx-i);
        }
        else{
            p[i]=1;
        }
        while(new_s[i+p[i]]==new_s[i-p[i]]){
            p[i]++;
        }
        if(i+p[i]>mx){
            mx=i+p[i];
            idx=i;
        }
    }
    int ans=0;
    for(int i=0;i<len2;i++){
        ans=max(ans,p[i]);
    }
    printf("%d\n",ans-1);
    return 0;
}