schtonn

schtonn

0%

Manacher

Posted on Edited on Valine:

前置知识

字符串基础操作。

引入

回文串，即 \(s=s_{rev}\)，也就是本身与反转相等。

想要找到字符串 \(s\) 中最大的回文子串，很容易想到的是一种复杂度为 \(O(n^2)\) 的朴素算法，也就是对于每一个点都向外扩展。

这里介绍一种复杂度为 \(O(n)\) 的最大回文子串算法，叫做 Manacher。

最大回文子串

求最大回文子串，可以转化为求对于每一个位置 i，求以 i 为中心的回文串半径 rad[i]。

然而由于偶数长度的回文串没有实际的“中心”，所以我们需要把偶数长度全部转化为奇数长度。

方法是：在每一位字符之间添加一个填充符号，比如 \(\mathtt{\$ }\)。如果原字符串是 \(\mathtt{schtonn}\)，那么就转化为 \(\mathtt{\$s\$c\$h\$t\$o\$n\$n\$ }\)。这样偶数长度的回文串 \(\mathtt{nn}\)，就变成了奇数长度的 \(\mathtt{\$n\$n\$ }\)。

Manacher

Manacher 算法维护了 l 和 r，记录右边界最靠右的回文子串的边界。

现在我们迭代 i，计算 rad[i]： - 如果 i>r： 直接运行朴素算法，尝试拓展 rad[i]，直到不符合回文串性质或者碰到边界。 - 如果 i<=r 这时可以尝试利用之前已计算出的结果。对于之前计算出的回文串，我们在大多数情况下认为 rad[i] 至少为之前计算的回文串的对应位置的值。通俗的说就是在一个大回文串内部的小回文串大小是相等的。

比如字符串 \(\mathtt{abacabaab}\)，我们先将其处理成 \(\mathtt{a\$b\$a\$c\$a\$b\$a\$a\$b}\)。

在第三位 \(\mathtt{b}\) 前都是朴素算法：

\[\begin{aligned}\mathtt{\underline{\underline a\space\underline\$\space b\space\$\space a}\space\$\space c\space\$\space a\space\$\space b\space\$\space a\space\$\space a\space\$\space b}\\\mathtt{1\space1\space3\space0\space0\space0\space0\space0\space0\space0\space0\space0\space0\space0\space0\space0\space0}\end{aligned}\]

到了第四位 \(\mathtt{\$}\)，算法认定这一位的 rad 至少为第二位的 rad 值，所以从 1 开始计算朴素算法。

经过一段时间后：

\[\begin{aligned}\mathtt{a\space\$\space b\space\$\space a\space\$\space c\space\$\space a\space\$\space \underline{b\space\$\space a\space\$\space a\space\$\space b}}\\\mathtt{1\space1\space3\space1\space2\space1\space7\space1\space2\space1\space4\space1\space2\space4\space2\space1\space0}\end{aligned}\]

这时应该计算最后一位的 \(\mathtt{b}\) 了，我们根据算法看出 rad 至少是对应位置的 4。然而正确结果却小于四，这是因为这部分已经超出了回文串的边界。所以 rad[i] 应该至少为到 r 的距离和对应位置 rad 值中的最小值。

代码

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
$include"bits/stdc++.h"
using namespace std;
int len,rad[2000020];
int maxid,maxr;
char fakes[1000010],s[2000020];
int main(){
    cin>>fakes;
    len=strlen(fakes);
    for(int i=0;i<=len*2;i+=2){
        s[i]='$';
        s[i+1]=fakes[(i+1)/2];
    }
    len=strlen(s);
    int l=0,r=-1;//区间边界
    for(int i=0;i<len;i++){
        int k;
        if(i>r)k=1;
        else k=min(rad[l+r-i],r-i);
        while(0<=i-k && i+k<len && s[i-k]==s[i+k]){
            k++;
        }
        rad[i]=k--;
        if(i+k>r){
            l=i-k;
            r=i+k;
        }
        if(rad[i]>maxr){
            maxid=i;
            maxr=rad[i];
        }
    }
    int ans=rad[maxid]-1;
    for(int i=maxid-ans;i<=maxid+ans;i++){
        if(s[i]!='$')cout<<s[i];
    }
    return 0;
}

我踩的坑

  • 加上了 \(\mathtt{\$ }\) 之后，数组空间需要开大两倍。