Manacher 基础篇
引言:
主要是用来复习 Manacher 的,但初学者也能看咯。
声明:
本篇文章中:
-
- 本篇文章的字符串前一般加空格(不加的会特殊声明),即真实字符串从
1 开始。
敬请注意。
Manacher 概述:
用途:
主要是用来线性处理回文串问题,求最长回文串长度等。
即时间复杂度为
拓展串及其原因:
我们可以观察到,回文串可以有一个回文中心:
a b c b a回文中心为c。a b c c b a回文中心为两个c中间的空。
显然我们不希望处理空格,所以我们可以给每个字母之间补上一个 #:
# a # b # c # b # a #回文中心为c。# a # b # c # c # b # a #回文中心为两个c中间的#。
这样我们所有的回文串便都为奇数长度了,也就是说中心都可以被表示为一个点。
寻找每个点为中心时的最长半径:
【暴力】:
显然的,我们可以对于每一个点向左右扩展,类似与这一份代码:
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]++;
}
}
处理类似于如下的字符串时,时间复杂度为
所以过不了。
【Manacher】:
对于寻找每一个点时,我们可以记录在此之前,回文串右端点最大的回文串的右端点
-
显然有对称点 $mid\times2-i$。 - $p_{mid\times2-i}\le r-i 那么
p_i 必然等于p_{mid\times2-i} ,且不再可以扩展,详细解释后边说明。-
p_{mid\times2-i} > r-i 这种情况可以取到
r-i ,且可以扩展,扩展次数均摊后大致为\mathcal{O}(m) ,m 表示拓展后字符串长度。
-
-
在区间外,无能为力。
这样看下来,时间复杂度为
然而凭什么呢?
Manacher 详细说明:
对于
对于
显然,如果你的对称点的扩展不超过大区间,那么你的扩展也不会超过大区间,扩展长度应当正好和对称区间扩展长度相同,复杂度
对于
显然对称点的扩展长度和
不难发现,
代码:
我们这里分两部分讲:
【拓展回文串】:
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 [国家集训队] 拉拉队排练
注意到要求一定为奇数,所以我们只跑中心为字母而不是 # 的即可。
对于计算答案,可以把每一组记录下来,从大往小加入,且按叠加来计算,因为如果
#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 回文串计数
我们可以计算出每一个中心的最大半径,那么就会存在半径长度除以二的回文串,显然我们可以根据右端点来记录回文串。
每一次用每个回文串的右端点更新
#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,因为
#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;
}
结语:
也许不久后会出提高篇,敬请期待。