manacher算法

应用

用来处理最长回文串问题。

模板

void init(){
    a[1]=-1;
    for(int i=1;i<=n;++i) a[i*2]=0,a[i*2+1]=ch[i]-'a'+1;
    tot=2*n+2,a[tot]=0;
}
void manacher(){
    init();
    for(int i=1;i<=tot;++i){
        if(i<r) p[i]=min(p[mid*2-i],r-i);
        else p[i]=0;
        while(i+p[i]+1<=tot && i-p[i]-1>=1 && a[i+p[i]+1]==a[i-p[i]-1]) p[i]++;
        if(i+p[i]>r) mid=i,r=i+p[i];
        ans=max(ans,p[i]);
    }
}

P4555

想到\(L[i],R[i]\)分别表示左端点/右端点为\(i\)时的最长回文串，则答案为\(\max_{i=2}^n(R[i-1]+L[i])\).

而\(L[i],R[i]\)数组可以用贪心，直接双指针处理。

设\(j\)为第一个满足\(j+p[j]\geq i\)的,在源字符串中位置为\(k\)，新字符串中位置为\(i\)的中间点，则\(R[k]=\min(p[j],i-j+1)\);

类似的\(L[k]=min(p[j],j-i+1)\)；

至于为什么贪心是对的，考虑右端点为\(i\)的回文串最长就是\(i-j+1\)的长度(指的是新字符串中的下标差)，因此如果有\(j\)满足\(j+p[j]\geq i\),那么\(j+1,j+2,...\)处的回文串一定短于\(j\)处的,即第一个满足上述式子的\(j\)处的回文串为所求最长串。可以看出\(j\)单调递增，复杂度\(O(n)\).

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int p[N],a[N],R[N],L[N];
char ch[N];
int n,tot,r,mid;
void init(){
    a[1]=-1;
    for(int i=1;i<=n;++i) a[i*2]=0,a[i*2+1]=ch[i]-'a'+1;
    tot=2*n+2,a[tot]=0;
}
void manacher(){
    init();
    for(int i=1;i<=tot;++i){
        if(i<r) p[i]=min(p[mid*2-i],r-i);
        else p[i]=0;
        while(i+p[i]+1<=tot && i-p[i]-1>=1 && a[i+p[i]+1]==a[i-p[i]-1]) p[i]++;
        if(i+p[i]>r) mid=i,r=i+p[i];
    }
}
int main(){
    scanf("%s",ch+1);n=strlen(ch+1);
    manacher();
    int j=0,i=0;
    for(int k=1;k<=n;++k){
        i=k*2+1;
        while(j+p[j]<i && j<=tot) ++j;
        R[k]=min(p[j],i-j+1);
    }
    j=tot;
    for(int k=n;k>=1;--k){
        i=k*2+1;
        while(i<j-p[j] && j>=1) --j;
        L[k]=min(p[j],j-i+1);
    }
    int ans=0;
    for(int i=2;i<=n;++i) ans=max(ans,R[i-1]+L[i]);
    printf("%d",ans);
    return 0;
}