专栏文章

自学Manacher

dde_mosyt
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqefe50
此快照首次捕获于
2025/12/04 03:27
3 个月前
此快照最后确认于
2025/12/04 03:27
3 个月前
查看原文

前文

time:2025.1.24
无事，自学OIwiki中Manacher算法

背景：P3805

【模板】Manacher

题目描述

给出一个只由小写英文字符 a,b,c,…y,z\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z 组成的字符串 SS ,求 SS 中最长回文串的长度 。
字符串长度为 nn。

输入格式

一行小写英文字符 a,b,c,⋯ ,y,z\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z 组成的字符串 SS。

输出格式

一个整数表示答案。
样例输入 #1
CPP
aaa
样例输出 #1
CPP
3

提示

1≤n≤1.1×1071\le n\le 1.1\times 10^7。

分析

显然，这道题的朴素做法是对于每一个点，遍历寻找最长的回文串，复杂度是 O(n)O(n)。
在这道题中显然过不去，因此似乎一眼看过去该问题并没有线性算法。
但是关于回文串的信息可用 一种更紧凑的方式表达：对于每个位置 i=0…n−1i = 0 \dots n - 1，我们找出值 d1[i]d_1[i] 和 d2[i]d_2[i]。二者分别表示以位置 ii 为中心的长度为奇数和长度为偶数的回文串个数。换个角度，二者也表示了以位置 ii 为中心的最长回文串的半径长度（半径长度 d1[i]d_1[i]，d2[i]d_2[i] 均为从位置 i 到回文串最右端位置包含的字符个数）。
举例来说，字符串 s=abababc以s[3]=bs = \mathtt{abababc} 以 s[3] = b 为中心有三个奇数长度的回文串，最长回文串半径为 33，也即 d1[3]=3d_1[3] = 3：
a b a bs3 a b⏞d1[3]=3 ca\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c
字符串 s=cbaabds = \mathtt{cbaabd} 以 s[3]=as[3] = a 为中心有两个偶数长度的回文串，最长回文串半径为 22，也即 d2[3]=2d_2[3] = 2：
c b a as3 b⏞d2[3]=2 dc\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d
因此关键思路是，如果以某个位置 ii 为中心，我们有一个长度为 ll 的回文串，那么我们有以 ii 为中心的长度为 l−2l - 2，l−4l - 4，等等的回文串。所以 d1[i]d_1[i] 和 d2[i]d_2[i] 两个数组已经足够表示字符串中所有子回文串的信息。

解法：Manacher算法

复杂度：O(n)O(n)

首先，为方便，我们称前文提及的 O(n2)O(n^2) 算法称之为朴素算法。
实现如下：
CPP
int d1[N],d2[N];
for(int i=0;i<s.size();i++){
  d1[i]=1;
  while (0<=i-d1[i]&&i+d1[i]<s.size()&&s[i-d1[i]]==s[i+d1[i]]){
    d1[i]++;
  }

  d2[i]=0;
  while (0<=i-d2[i]-1&&i+d2[i]<s.size()&&s[i-d2[i]-1]==s[i+d2[i]]){
    d2[i]++;
  }
}
现在我们以 d1[i]d_1[i] 的计算方法为例，介绍一下算法的过程，因为计算 d2[i]d_2[i] 的方法只需要对 d1[i]d_1[i] 的方法做一些小修改。
为了快速计算，我们维护已找到的最靠右的子回文串的 边界 (l,r)(l, r)（即具有最大 rr 值的回文串，其中 ll 和 rr 分别为该回文串左右边界的位置）。初始时，我们置 l=0l = 0 和 r=−1r = -1（−1-1需区别于倒序索引位置，这里可为任意负数，仅为了循环初始时方便）。
现在假设我们要对下一个 ii 计算 d1[i]d_1[i]，而之前所有 d1[]d_1[] 中的值已计算完毕。我们将通过下列方式计算：
如果 ii 位于当前子回文串之外，即 i>ri > r，那么我们调用朴素算法（即用 whilewhile 循环找出）。
因此我们将连续地增加 d1[i]d_1[i]，同时在每一步中检查当前的子串 [i−d1[i]…i+d1[i]][i - d_1[i] \dots i + d_1[i]]（d1[i]d_1[i] 表示半径长度，下同）是否为一个回文串。如果我们找到了第一处对应字符不同，又或者碰到了 ss 的边界，则算法停止。在两种情况下我们均已计算完 d1[i]d_1[i]。此后，仍需记得更新 (l,r)(l, r)。
现在考虑 i≤ri \le r 的情况。我们将尝试从已计算过的 d1[]d_1[] 的值中获取一些信息。首先在子回文串 (l,r)(l, r) 中反转位置 ii，即我们得到 j=l+(r−i)j = l + (r - i)。现在来考察值 d1[j]d_1[j]。因为位置 jj 同位置 ii 对称，我们 几乎总是 可以置 d1[i]=d1[j]d_1[i] = d_1[j]。该想法的图示如下（可认为以 jj 为中心的回文串被 “拷贝”至以 ii 为中心的位置上）：
… sl … sj−d1[j]+1 … sj … sj+d1[j]−1⏟palindrome … si−d1[j]+1 … si … si+d1[j]−1⏟palindrome … sr⏞palindrome …\ldots\ \overbrace{ s_l\ \ldots\ \underbrace{ s_{j-d_1[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_1[j]-1} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_1[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_1[j]-1} }_\text{palindrome}\ \ldots\ s_r }^\text{palindrome}\ \ldots
然而有一个棘手的情况需要被正确处理：当「内部」的回文串到达「外部」回文串的边界时，即 j−d1[j]+1≤lj - d_1[j] + 1 \le l（或者等价的说，i+d1[j]−1≥ri + d_1[j] - 1 \ge r）。因为在「外部」回文串范围以外的对称性没有保证，因此直接置 d1[i]=d1[j]d_1[i] = d_1[j] 将是不正确的：我们没有足够的信息来断言在位置 i 的回文串具有同样的长度。
实际上，为了正确处理这种情况，我们应该「截断」回文串的长度，即置 d1[i]=r−id_1[i] = r - i。之后我们将运行朴素算法以尝试尽可能增加 d1[i]d_1[i] 的值。
该种情况的图示如下（以 jj 为中心的回文串已经被截断以落在「外部」回文串内）：
… sl … sj … sj+(j−l)⏟palindrome … si−(r−i) … si … sr⏟palindrome⏞palindrome ……………⏟try moving here\ldots\ \overbrace{ \underbrace{ s_l\ \ldots\ s_j\ \ldots\ s_{j+(j-l)} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)}\ \ldots\ s_i\ \ldots\ s_r }_\text{palindrome} }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here}
该图示显示出，尽管以 jj 为中心的回文串可能更长，以致于超出「外部」回文串，但在位置 ii，我们只能利用其完全落在「外部」回文串内的部分。然而位置 ii 的答案可能比这个值更大，因此接下来我们将运行朴素算法来尝试将其扩展至「外部」回文串之外，也即标识为 "try moving here" 的区域。
最后，仍有必要提醒的是，我们应当记得在计算完每个 d1[i]d_1[i] 后更新值 (l,r)(l, r)。
这时候我们就可以发现其实对于 d2[]d_2[] 的计算其实与 d1[]d_1[] 十分类似。

实现 解法

CPP
#include<bits/stdc++.h>
using namespace std;
#define N 11000005
string s;
int d1[N],d2[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    for(int i=0,l=0,r=-1;i<s.size();i++){
        int k;
        if(i>r) k=1;    
        else k=min(d1[l+r-i],r-i+1);
        while(0<=i-k&&i+k<s.size()&&s[i-k]==s[i+k]) k++;
        d1[i]=k--; 
        if(i+k>r){
            l=i-k;
            r=i+k;
        }
    }
    for(int i=0,l=0,r=-1;i<s.size();i++){
        int k;
        if(i>r) k=0;
        else k=min(d2[l+r-i+1],r-i+1);
        while(0<=i-k-1&&i+k<s.size()&&s[i-k-1]==s[i+k]) k++;
        d2[i]=k--;
        if(i+k>r){
            l=i-k-1;
            r=i+k;
        }
    }
    int ans=0;
    for(int i=0;i<s.size();i++){
        ans=max(ans,d1[i]*2-1);
        ans=max(ans,d2[i]*2);
    }
    cout<<ans<<'\n';
    return 0;  
}
--参考文献：OIwikiOIwiki

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...