洛谷 P3805【模板】manacher算法

题目链接：https://www.luogu.com.cn/problem/P3805

Manacher算法$O(n)$：

求以每个字符为中心的最长回文串的半径：
如果要求可以以字符间隙为回文中心，就要在每两个字符之间加入一个’#’，在开头加上'$'，然后再解决。

$pos$表示回文字串的对称轴，$mx$表示回文串在最右右边界，很明显$2 imes pos-i$即为$i$关于$pos$的对称点。

令$r_i$为以$i$为中心的最长回文半径。从左往右依次求$r$数组：
若$i>mx$，即$i$不在所已知的回文串的范围内，那么就让$r_i$从$1$开始计算。

若$ileq mx$：

　　设$j$为$i$关于$pos$的对称点，即$j=(2 imes pos-i)$。

　　1)，若$r_j>mx-i$，那么不能保证在mx右边仍为回文，所以这时$r_i=mx-i$。

　　2)，若$r_jleq mx-i$，那么根据对称性可以直接得到，$r_i=r_j$。

　　综上所述，$r_i=min(r_j,mx-i)$。

然后开始暴力往两边扩展，看看是否满足回文。如果右端点扩展到mx右边，则需要更新$mx$和$pos$。

最后不难发现,$r_i-1$中的最大值即为答案，即$ans=max(ans,r_i-1)$。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=51000050;
char str[maxn],s[maxn];
int r[maxn];

int manacher(int len){
    int t=0,ans=0;
    s[0]='$';s[++t]='#';
    for(int i=1;i<=len;i++){
        s[++t]=str[i];
        s[++t]='#';
    }
    int pos=0,mx=0;
    for(int i=1;i<=t;i++){
        if(i>mx) r[i]=1;
        else r[i]=min(r[2*pos-i],mx-i);
        while(i-r[i]>=1&&i+r[i]<=t&&s[i+r[i]]==s[i-r[i]]) r[i]++;
        if(i+r[i]>mx){
            mx=i+r[i];
            pos=i;
        }
        ans=max(ans,r[i]-1);
    }
    return ans;
}

int main(){
    scanf("%s",str+1);
    printf("%d
",manacher(strlen(str+1)));
    return 0;
}