Manacher 基础篇

· · 算法·理论

引言:

主要是用来复习 Manacher 的,但初学者也能看咯。

声明:

本篇文章中:

敬请注意。

Manacher 概述:

用途:

主要是用来线性处理回文串问题,求最长回文串长度等。

即时间复杂度为 \mathcal{O}(n)。

拓展串及其原因:

我们可以观察到,回文串可以有一个回文中心:

显然我们不希望处理空格,所以我们可以给每个字母之间补上一个 #:

这样我们所有的回文串便都为奇数长度了,也就是说中心都可以被表示为一个点。

寻找每个点为中心时的最长半径:

【暴力】:

显然的,我们可以对于每一个点向左右扩展,类似与这一份代码:

 for(int i=1;i<=m;i++){
   p[i]=0;
   while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
     p[i]++;
   }
 }

处理类似于如下的字符串时,时间复杂度为 \mathcal{O}(n^2):

aaaaa\dots

所以过不了。

【Manacher】:

对于寻找每一个点时,我们可以记录在此之前,回文串右端点最大的回文串的右端点 r 和中点 mid,对于一个新的回文中心 i,我们可以分情况考虑:

这样看下来,时间复杂度为 \mathcal{O}(m),是我们想要的。

然而凭什么呢?

Manacher 详细说明:

对于 i\ge r 的,在区间外只能自己一步步找了,不用解释。

对于 p_{mid\times2-i}\le r-i 的,如图:

显然,如果你的对称点的扩展不超过大区间,那么你的扩展也不会超过大区间,扩展长度应当正好和对称区间扩展长度相同,复杂度 \mathcal{O}(1),仅赋值。

对于 p_{mid\times2-i} > r-i 的,如图:

显然对称点的扩展长度和 i 不一定相等,但是可以确定的是,如果超过了,那么在 r 之内的部分必然回文,所以我们可以直接将区间长度看作是 r-i,同时再向后续扩展。

不难发现,r 只增不减,所以均摊下来复杂度 \mathcal{O}(m)。

代码:

我们这里分两部分讲:

【拓展回文串】:

void add(){
    str="$";
    int len=s.size();
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}

纯模拟,我们记得首尾也加上 #,可以保证两端一定不会是字符。

【计算最大回文】:

void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i+p[i]+1]==str[i-p[i]-1]){
          p[i]++;
        }
        if(i+p[i]>r){
          r=p[i]+i;
          mid=i;
        }
        ans=max(ans,p[i]);
    }
}

我们主要注意下:每次结束一定要找右端点最大的,而不是半径最大的,右端点尽可能的大才能保证每一次都是右端点再往右移动,否则可能复杂度有误。

练习:

题单。

P3805 【模板】Manacher

模板题,就按照前面的两个函数写完后输入,执行函数,输出即可。

#include<bits/stdc++.h>
using namespace std;
const int NA=1.1e7;
int m,p[NA*2+5],ans;
string s,str;
void add(){
    str="$";
    int len=s.size();
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i+p[i]+1]==str[i-p[i]-1]){
          p[i]++;
        }
        if(i+p[i]>r){
          r=p[i]+i;
          mid=i;
        }
        ans=max(ans,p[i]);
    }
}
int main(){
    cin>>s;
    add();
    manacher();
    cout<<ans<<"\n";
    return 0;
}

P3501 [POI 2010] ANT-Antisymmetry

本质上是正好相反的,不过 Manancher 所要的性质还在,因为如果左区间符合,那么右区间也符合,只是形态正好相反,答案不变。

比对的时候 01 和 # 两种情况都判断一下便可以了。

记得开 long long。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=1e6+5;
int m,len,p[NA],ans;
string s,str;
void add(){
    str="$";
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i+=2){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&(str[i-p[i]-1]+str[i+p[i]+1]=='0'+'1'||str[i-p[i]-1]+str[i+p[i]+1]=='#'+'#')){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        ans=ans+p[i]/2;
    }
}
signed main(){
    cin>>len;
    cin>>s;
    add();
    manacher();
    cout<<ans<<"\n";
    return 0;
}

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

注意到要求一定为奇数,所以我们只跑中心为字母而不是 # 的即可。

对于计算答案,可以把每一组记录下来,从大往小加入,且按叠加来计算,因为如果 5 可以,那么 3 必然可以。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=2e6+5;
const int mod=19930726;
int m,len,k,p[NA],ans=1;
string s,str;
vector<int> v; 
int qpow(int a,int b){
    int cul=1;
    while(b){
        if(b&1) cul=cul*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return cul;
}
void add(){
    str="$";
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=2;i<=m;i+=2){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        v.push_back(p[i]);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int cnt=0;
    for(int i=len;i>=1;i--){
        if((i&1)==0) continue;
        while(cnt<v.size()&&v[cnt]>=i){
            cnt++;
        }
        if(cnt<k){
            ans=ans*qpow(i,cnt)%mod;
            k-=cnt;
        }
        else{
            ans=ans*qpow(i,k)%mod;
            k=0;
            break;
        }
    }
}
signed main(){
    cin>>len>>k;
    cin>>s;
    add();
    manacher();
    if(k!=0) cout<<"-1\n";
    else cout<<ans<<"\n";
    return 0;
}

P12213 [蓝桥杯 2023 国 Python B] 最长回文前后缀

观察性质,我们可以发现,如果一个回文串正着可以,那么按中心分为两半后左右颠倒也可以,例如:abba 可以变为 baab。

那么我们可以转换一下:

显然就两种情况:前缀长度大于等于后缀,前缀长度小于后缀,我们可以发现两种情况的共同点:本质上前缀和后缀都有一部分是对称的。

那么我们不妨求出最长的且拼在一起的前缀和后缀,去掉后找到最大区间的长度,计算与最长前缀的长度的和就是答案了。

那么为什么一定会选最长前缀,因为你的前缀如果不是最长前缀,那么后面尽管那个区间可以补上,但绝对不会超过,所以没有必要去考虑那种情况。

最大区间的长度要注意只有包含边界的有效。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=2e6+5;
int m,p[NA],ans,cnt;
string s,s1,s2,str;
void add(){
    str="$";
    int len=s.size();
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        if(i-p[i]==1){
            ans=max(ans,p[i]);
        }
    }
}
signed main(){
    cin>>s1;
    s2=s1;
    reverse(s2.begin(),s2.end());
    while(cnt<s1.size()&&s1[cnt]==s2[cnt]){
        cnt++;
    }
    s=s1.substr(cnt);
    add();
    manacher();
    s=s2.substr(cnt);
    add();
    manacher();
    cout<<ans+cnt*2<<"\n";
    return 0;
}

P1872 回文串计数

我们可以计算出每一个中心的最大半径,那么就会存在半径长度除以二的回文串,显然我们可以根据右端点来记录回文串。

每一次用每个回文串的右端点更新 cnt 数组,用左端点减二来计算答案就可以了。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=2e6+5;
int m,p[NA],ans,cnt[NA];
string s,str;
void add(){
    str="$";
    int len=s.size();
    for(int i=0;i<len;i++){
      str+="#";
      str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        for(int j=i;j<=i+p[i];j++){
            if(j%2==1) continue;
            cnt[j]++;
        }
        for(int j=i-p[i];j<=i;j++){
            if(j%2==1) continue;
            ans+=cnt[j-2];
        }
        if(i%2==0) cnt[i]+=cnt[i-2];
    }
}
signed main(){
    cin>>s;
    add();
    manacher();
    cout<<ans<<"\n";
    return 0;
}

AT_abc398_f [ABC398F] ABCBA

显然可以发现,我们只需要找到后缀最大回文串,然后以这个回文串的中心为中心来补齐即可。

如果不是后缀回文串的中心的话,我们显然的发现是无解的,因为这个回文串再延伸出去一点他都是不回文的了。

至于为什么不可以是前缀,题目要求的,切记切记啊。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=2e6+5;
int m,len,p[NA],ans=-1,id,cnt[NA];
string s,str;
void add(){
    str="$";
    len=s.size();
    for(int i=0;i<len;i++){
        str+="#";
        str+=s[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        if(i+p[i]==m){
            if(p[i]>=ans){
                ans=p[i];
                id=i;
            }
        }
    }
    int L=(id-p[id]+1)/2,R=(id+p[id]-1)/2;
    cout<<s;
    for(int i=L-1-1;i>=0;i--){
        cout<<s[i];
    }
}
signed main(){
    cin>>s;
    add();
    manacher();
    return 0;
}

P13885 [蓝桥杯 2023 省 Java/Python A] 反异或 01 串

读题可知,我们如果想尽可能多省,那么就找到一个包含 1 最多的回文串即可,然后我们就可以省去该回文串一半的 1 了。

值得注意的是,如果回文串是奇数个字符,那么中间必然为 0,因为 x\oplus x=0。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NA=2e6+5;
int m,len,p[NA],ans,id,cnt[NA];
string s,str;
void add(){
    str="$";
    len=s.size();
    for(int i=0;i<len;i++){
        str+="#";
        str+=s[i];
        if(s[i]=='1'){
          cnt[i+1]++;
        }
        cnt[i+1]+=cnt[i];
    }
    str+="#";
    str+="@";
    m=len*2+1;
}
void manacher(){
    int r=0,mid=0;
    for(int i=1;i<=m;i++){
        p[i]=(i<r?min(p[2*mid-i],r-i):0);
        while(i-p[i]-1>=1&&i+p[i]+1<=m&&str[i-p[i]-1]==str[i+p[i]+1]){
            p[i]++;
        }
        if(i+p[i]>r){
            r=p[i]+i;
            mid=i;
        }
        int l=(i-p[i]+1)/2,r=(i+p[i]-1)/2;
        if((i%2==0&&str[i]=='0')||i%2==1) ans=max(ans,cnt[r]-cnt[l-1]);
    }
}
signed main(){
    cin>>s;
    add();
    manacher();
    cout<<cnt[len]-ans/2<<"\n";
    return 0;
}

结语:

也许不久后会出提高篇,敬请期待。