manacher

yanmingqian · 2025-09-02 21:05:39 · 算法·理论

引入

一种求字符串中最长回文串的算法，好像是今年刚被扔到提高级大纲的。

先来引入一个很好的记录回文串方式：我们定义 d_i 表示以 i 为中心的最长回文串半径。然后我们就可以用 O(n) 的空间复杂度来记录一个字符串中的回文串了。

显然有朴素的时间复杂度 O(n^2) 做法来求 d_i：遍历每个 i，每次向两边暴力扩展。

解法

考虑更好的做法。manacher 就是一种实现异常简单的解决这种问题的算法，而且拥有高贵的 O(n) 时间复杂度。

首先我们要对原始字符串做一点小处理。如果我们直接求一个字符串的回文串，那么我们需要分为回文串长度为奇数和长度为偶数的情况进行讨论，这样比较麻烦。有一种更好的解决方式：我们在原串的开头结尾以及两两字符之间插入一个原串中不存在的特殊字符，如 #。这样我们再对这个新字符串进行求解，就能够让所有回文串长度都变成奇数，会方便很多。对于长度的影响是每个回文串的半径变为了原来的两倍加一。

接下来是算法的核心。我们假设现在枚举到了 i 位置，且 d_1 到 d_{i-1} 我们已经全部求解完毕。同时我们在之前求解的过程中记录下了当前求解的回文串中最靠右（也就是右端点最大）的一个的中间位置 mid 和右端点 r。接下来我们考虑如何求 d_i。需要分情况讨论：

我们来梳理一下算法思路：

1. 设 k 为当前的 d_i。若 i\le r，先将 k 设为 \min(d_{2\times mid -1},r-i)，否则将 k 设为 1；
2. 调用朴素算法，暴力扩展 k；
3. 更新 mid 和 r。

代码如下：

int n=s.size(),mid=0,r=-1;
for(int i=0;i<n;i++){
    int k=(i<=r)?min(d[mid*2-i],r-i+1):1;
    while(i>=k&&i+k<n&&s[i-k]==s[i+k]) k++;  
    d[i]=k--;
    if(i+k>r) r=i+k,mid=i;
}

时间复杂度

这个算法乍一看好像只是朴素算法的优化，可能会退化为 O(n^2)，但是实际上，注意到朴素算法的每次迭代均会使 r 增加 1，以及 r 在算法运行过程中从不减小。这两个观察告诉我们朴素算法总共会进行 O(n) 次迭代。（引自 OI-wiki）

题目

P3805 【模板】manacher

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

板子，直接套就行。注意我们求得的 d_i 实际上是以 i 为中心的最长回文串的长度加一，因此最后输出时要减一。

需要注意的是，一开始在两两字符间插入特殊字符时，不要使用 s=s+c+'#'，而应使用 s+=c,s+='#'。前者很慢。

#include<iostream>
using namespace std;
const int N=2.2e7+10;
int d[N];
int main(){
    string s="#";char c=getchar();
    while(c>='a'&&c<='z') s+=c,s+='#',c=getchar();
    int n=s.size(),mid=0,r=-1,ans=0;
    for(int i=0;i<n;i++){
        int k=(i<=r)?min(d[mid*2-i],r-i+1):1;
        while(i>=k&&i+k<n&&s[i-k]==s[i+k]) k++;
        ans=max(ans,d[i]=k--);
        if(i+k>r) r=i+k,mid=i;
    }
    cout<<ans-1;
    return 0;
}

P1659 [国家集训队] 拉拉队排练

给定长度为 n 的字符串 S 和 k，求 S 中所有回文串的长度中前 k 大的乘积模 19930726 的值，回文串数不足 k 个输出 -1。

先 manacher，然后我们用一个桶来记录每个 d_i 值的数量。接着从大到小枚举长度，每次快速幂增加答案即可。

#include<iostream>
using namespace std;
#define int long long
const int N=1e6+10,mod=19930726;
int d[N],t[N];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
signed main(){
    int n,k;string s;
    cin>>n>>k>>s;
    int mid=0,r=-1;
    for(int i=0;i<n;i++){
        int k=(i<=r)?min(d[mid*2-i],r-i+1):1;
        while(i>=k&&i+k<n&&s[i-k]==s[i+k]) k++;
        d[i]=k--;
        if(i+k>r) r=i+k,mid=i;
        t[d[i]*2-1]++;
    }
    if(!(n&1)) n--;
    int sum=0,ans=1;
    for(int i=n;i>=1;i-=2){
        sum+=t[i];
        if(sum>k){ans=ans*qpow(i,k)%mod;break;}
        else ans=ans*qpow(i,sum)%mod,k-=sum;
    }
    cout<<((sum>=k)?ans:-1);
    return 0;
}

P4555 [国家集训队] 最长双回文串

输入长度为 n 的串 S，求 S 的最长双回文子串 T，即可将 T 分为两部分 X, Y（|X|,|Y|≥1）且 X 和 Y 都是回文串。

我们考虑记录以 i 为左右端点的最大回文串半径，分别记作 ld_i 和 rd_i。在 manacher 的过程中，我们每次求得了当前的 d_i 值，就可以更新 ld_{i-d_i} 和 rd_{i+d_i}。在求解结束后，我们再来递推出 i-d_i 和 i+d_i 中间点的 ld 和 rd 值：每向前或向后到下一个位置，回文串的长度都会 -2，这样就可以递推出来所有 ld 和 rd 值，接着统计答案即可。

#include<iostream>
using namespace std;
const int N=2e5+10;
int d[N];
int ld[N],rd[N];
int main(){
    string s="#";char c=getchar();
    while(c>='a'&&c<='z') s+=c,s+='#',c=getchar();
    int n=s.size(),mid=0,r=-1,ans=0;
    for(int i=0;i<n;i++){
        int k=(i<=r)?min(d[mid*2-i],r-i+1):1;
        while(i>=k&&i+k<n&&s[i-k]==s[i+k]) k++;
        d[i]=k--;
        if(i+k>r) r=i+k,mid=i;
        ld[i-k]=max(ld[i-k],k);rd[i+k]=max(rd[i+k],k);
    for(int i=2;i<n;i+=2) ld[i]=max(ld[i],ld[i-2]-2);
    for(int i=n-1;i>=0;i-=2) rd[i]=max(rd[i],rd[i+2]-2);
    for(int i=0;i<n;i++) if(ld[i]&&rd[i]) ans=max(ans,ld[i]+rd[i]);  //注意必须ld[i]和rd[i]均不为0时才可统计
    cout<<ans;
    return 0;
}

P4287 [SHOI2011] 双倍回文

对于给定的字符串，计算它的最长双倍回文子串的长度。双倍回文串的定义如下：若 x 为双倍回文串，则其长度必须为 4 的倍数，其本身为回文串，且从中间分成的前后两部分都必须同样是回文串。

我们考虑在 manacher 中每次更新 r 的时候来计算答案。此时我们已经求出了一些新的回文串，对于这些回文串，我们枚举可能的以当前 i 为中心的双倍回文串的右端点，并验证这个串的前半部分是否同样是回文串，如果是就更新答案。

#include<iostream>
using namespace std;
const int N=1e6+10;
int d[N];
int main(){
    int n;
    cin>>n;
    string s="#";char c=getchar();
    while(c<'a'||c>'z') c=getchar();while(c>='a'&&c<='z') s+=c,s+='#',c=getchar();
    int mid=0,r=-1,ans=0;n=n<<1|1;
    for(int i=0;i<n;i++){
        int k=((i<=r)?min(d[mid*2-i],r-i+1):1);
        while(i>=k&&i+k<n&&s[i-k]==s[i+k]) k++;
        d[i]=k--;
        if(i+k>r){  //找到了一个新的回文串后，我们考虑在这个回文串里找新的双倍回文串（以i为中心）
            if(!(i&1))  //回文串对应长度为偶数
                for(int j=max(r,i+4);j<i+d[i];j++)  //遍历新扩展的区域,j是潜在的双倍回文串右边界
                    if((j-i)%4==0&&d[i-(j-i)/2]>=(j-i)/2)  //长度为4的倍数且左半部分是回文串
                        ans=max(ans,j-i);
            r=i+k,mid=i;
        }
    }
    cout<<ans;
    return 0;
}