Eternity

Until The End

Manacher算法

发表于 分类于 ，
本文字数： 1.7k 阅读时长 ≈ 2 分钟

似乎没什么用的字符串算法。

用于在线性时间内匹配回文子串。

回文串

字符串的回文串分为两种：奇子回文串和偶子回文串，类似于中位数的解法，奇子回文串的回文中心是一个字符，而偶子回文串的回文中心是两个字符。例如：

$abcdcba$ 是一个奇回文串，其回文中心是 $d$ ；

$abcddcba$ 是一个偶回文串，其回文中心是 $dd$ 。

回文匹配

有一个很显然的性质，回文中心的两端应该是相等的，那么，就有一种 $\mathcal O(n^2)$ 的暴力匹配思路：

枚举回文中心，向两端暴力匹配。

但有一个问题，那就是，我们无法枚举偶回文串的回文中心，所以考虑转换字符串：

$abccba\Rightarrow |a|b|c|c|b|a|$

即插入隔板，使其回文中心变成一个隔板。但这样的话，我们还需要类似于平衡树内的卫兵，即在左右分别插入一个奇奇怪怪的字符：

$!|a|b|c|c|b|a|?$

以保证在匹配的时候，不会把空字符算进匹配中。

Manacher

这个算法是在暴力的基础上进行了一个优化。因为有字符串算法线性公理（因为 $\text{Kmp,ExKmp,SAM}$ 等字符串相关的算法都是线性复杂度），所以不难猜出，$\text{Manacher}$ 算法（俗称马拉车算法）也是线性复杂度。

我们设当前的已找到的回文串的最右端点为 $mr$ ，$mr$ 所属的回文串的回文中心为 $mid$ ，注意，这里的字符串已经经过了扩倍处理。

设函数 $p(i)$ 表示以 $i$ 为回文中心的回文串的最长半径（即回文中心到其中一个端点的距离，计算公式为 $r-mid$ 或 $mid-l$），我们假定当前 $p(1)\sim p(i-1)$ 已经计算好了。

那么当前枚举的 $i$ 一定满足 $mid\leq i\leq mr$ ，那么，则一定有 $str[i]=str[2mid-i]$ ，这是回文的定义，不必多述。也正因为这样，所以会有 $p[i]=p[2mid-i]$ ，但我们无法保证是否满足 $p[i]\geq p[2mid-i]$ ，所以还需要对 $i$ 进行暴力拓展。然后更新答案。

当然，我们也要更新 $mid$ 和 $mr$ ，因为我们不需要保证当前 $mid$ 所在的回文串是最长的，只需要 $mr$ 尽可能大已让暴力拓展的次数尽量少。所以，只要当前拓展的回文大于了 $mr$ ，就直接更新就好了。

代码就三行，时间复杂度 $\mathcal O(n)$ ，虽然我不会证，但反正 $1.1\times 10^7$ 能过即可。

回文子串线性匹配的双倍经验

AC Code 
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
#include<bits/stdc++.h>
const int MAXN=1.1e7+10;
char S[MAXN],Str[MAXN<<1];
int N,Cnt,P[MAXN<<1],ans;
int main()
{
    scanf("%s",S+1);
    N=strlen(S+1);
    Str[++Cnt]='~',Str[++Cnt]='#';
    for(int i=1;i<=N;++i) Str[++Cnt]=S[i],Str[++Cnt]='#';
    Str[++Cnt]='!';
    for(int i=2,mr=0,mid=0;i<Cnt;++i)
    {
        if(i<=mr) P[i]=std::min(P[(mid<<1)-i],mr-i+1);
        else P[i]=1;
        while(Str[i-P[i]]==Str[i+P[i]]) ++P[i];
        if(i+P[i]>mr) mr=i+P[i]-1,mid=i;
        ans=std::max(ans,P[i]);
    }
    printf("%d",ans-1);
    return 0;
}
/*
aaa
*/

这个算法用处不大，回文匹配也可以用字符串哈希水到 $\mathcal O(n\log n )$ ，没必要卡这个。

相关文章