Manacher，不知道怎么进入提高级大纲的老登

下文的所有字符串，下标默认从

1

开始。

在字符串的开头结尾，以及两字符之间，插入一个符号 #，比如 manacher 字符串就变为 #m#a#n#a#c#h#e#r#。这样做是为了让两种回文子串的情况（长度为奇、偶）归并为一种，减少分类讨论。

Manacher 算法，可以在线性复杂度内，处理出

f

数组，其中

f_i

表示以下标

i

的字符为中心，最大的回文子串长度。

假设已经处理了

f_1,f_2,\dots,f_{i-1}

的值，需要求

f_i

的值，且已经知道了以位置

t\in[1,i-1]

为中心，所有回文串的右端点的最大值为

R

，其对应的回文中心为

C

。

对于求

f_i

，分两种情况：

$i>R$ ，这个时候已有条件无法处理，只能暴力扩展。
$i\leq R$ ，图示如下：

这个时候，对

i\leq R

的情况继续讨论：

若 $i'$ 的回文区域在 $[L,R]$ 内，但左端没到 $L$ ：

显然，

f_i=f_{i'}

。

若 $i$ 的回文区域的左端超过了 $L$ ：

这个时候会发现，第

1

段与第

3

段相同，第

3

段与第

4

段相同。如果

i

可以扩展直至包含

2,4

段，则

2,4

段也相同，那么

1,2

段就相同。

但此时以

C

为中心的回文串没有扩展到

1,2

段，故矛盾，也就是这种情况不存在。

若 $i$ 的回文区域的左端正好是 $L$ ：

这个时候不好判断，暴力扩展即可。

该算法流程完毕，~~感性理解~~可以得出复杂度为线性。

代码

CPP

cin>>str,s="#";
for (auto i:str)
    s+=i,s+='#';
n=s.size(),s=' '+s;
fo(i,1,n){
    if (i>r) p[i]=1;
    else p[i]=min(r-i,p[2*t-i]);
    while (i+p[i]<=n&&i-p[i]>=1&&s[i+p[i]]==s[i-p[i]])
        p[i]++;
    if (p[i]+i>r)
        r=i+p[i],t=i;
    mx=max(mx,p[i]-1);
}

图片出处：link。

Manacher，不知道怎么进入提高级大纲的老登

文章操作

相关推荐

评论

Manacher，不知道怎么进入提高级大纲的老登