自学Manacher

· · 算法·理论

前文

time:2025.1.24

无事，自学OIwiki中Manacher算法

背景：P3805

【模板】Manacher

题目描述

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

字符串长度为 n。

输入格式

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

输出格式

一个整数表示答案。

样例输入 #1
aaa
样例输出 #1
3

提示

## 分析 显然，这道题的朴素做法是对于每一个点，遍历寻找最长的回文串，复杂度是 $O(n)$。 在这道题中显然过不去，因此似乎一眼看过去该问题并没有线性算法。 但是关于回文串的信息可用 一种更紧凑的方式表达：对于每个位置 $i = 0 \dots n - 1$，我们找出值 $d_1[i]$ 和 $d_2[i]$。二者分别表示以位置 $i$ 为中心的长度为奇数和长度为偶数的回文串个数。换个角度，二者也表示了以位置 $i$ 为中心的最长回文串的半径长度（半径长度 $d_1[i]$，$d_2[i]$ 均为从位置 i 到回文串最右端位置包含的字符个数）。 举例来说，字符串 $s = \mathtt{abababc} 以 s[3] = b$ 为中心有三个奇数长度的回文串，最长回文串半径为 $3$，也即 $d_1[3] = 3$： $a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c

字符串 s = \mathtt{cbaabd} 以 s[3] = a 为中心有两个偶数长度的回文串，最长回文串半径为 2，也即 d_2[3] = 2：

c\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d

因此关键思路是，如果以某个位置 i 为中心，我们有一个长度为 l 的回文串，那么我们有以 i 为中心的长度为 l - 2，l - 4，等等的回文串。所以 d_1[i] 和 d_2[i] 两个数组已经足够表示字符串中所有子回文串的信息。

解法：Manacher算法

复杂度：O(n)

首先，为方便，我们称前文提及的 O(n^2) 算法称之为朴素算法。

实现如下：

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]++;
  }
}

现在我们以 d_1[i] 的计算方法为例，介绍一下算法的过程，因为计算 d_2[i] 的方法只需要对 d_1[i] 的方法做一些小修改。

为了快速计算，我们维护已找到的最靠右的子回文串的 边界 (l, r)（即具有最大 r 值的回文串，其中 l 和 r 分别为该回文串左右边界的位置）。初始时，我们置 l = 0 和 r = -1（-1需区别于倒序索引位置，这里可为任意负数，仅为了循环初始时方便）。

现在假设我们要对下一个 i 计算 d_1[i]，而之前所有 d_1[] 中的值已计算完毕。我们将通过下列方式计算：

如果 i 位于当前子回文串之外，即 i > r，那么我们调用朴素算法（即用 while 循环找出）。

因此我们将连续地增加 d_1[i]，同时在每一步中检查当前的子串 [i - d_1[i] \dots i + d_1[i]]（d_1[i] 表示半径长度，下同）是否为一个回文串。如果我们找到了第一处对应字符不同，又或者碰到了 s 的边界，则算法停止。在两种情况下我们均已计算完 d_1[i]。此后，仍需记得更新 (l, r)。

现在考虑 i \le r 的情况。我们将尝试从已计算过的 d_1[] 的值中获取一些信息。首先在子回文串 (l, r) 中反转位置 i，即我们得到 j = l + (r - i)。现在来考察值 d_1[j]。因为位置 j 同位置 i 对称，我们 几乎总是 可以置 d_1[i] = d_1[j]。该想法的图示如下（可认为以 j 为中心的回文串被 “拷贝”至以 i 为中心的位置上）：

\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 - d_1[j] + 1 \le l（或者等价的说，i + d_1[j] - 1 \ge r）。因为在「外部」回文串范围以外的对称性没有保证，因此直接置 d_1[i] = d_1[j] 将是不正确的：我们没有足够的信息来断言在位置 i 的回文串具有同样的长度。

实际上，为了正确处理这种情况，我们应该「截断」回文串的长度，即置 d_1[i] = r - i。之后我们将运行朴素算法以尝试尽可能增加 d_1[i] 的值。

该种情况的图示如下（以 j 为中心的回文串已经被截断以落在「外部」回文串内）：

\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}

该图示显示出，尽管以 j 为中心的回文串可能更长，以致于超出「外部」回文串，但在位置 i，我们只能利用其完全落在「外部」回文串内的部分。然而位置 i 的答案可能比这个值更大，因此接下来我们将运行朴素算法来尝试将其扩展至「外部」回文串之外，也即标识为 "try moving here" 的区域。

最后，仍有必要提醒的是，我们应当记得在计算完每个 d_1[i] 后更新值 (l, r)。

这时候我们就可以发现其实对于 d_2[] 的计算其实与 d_1[] 十分类似。

实现 解法

#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;  
}

--参考文献：OIwiki