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

_2eyks · 2025-10-28 21:09:38 · 个人记录

下文的所有字符串，下标默认从 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\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：

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

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

:::info[代码]

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。