Manacher总结

字符串算法——Manacher

我的代码

学习：yyb
luogu题目模板
xzy的模板

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 51000100
using namespace std;
const int Inf=1e9;
int n,ans=1;
int p[N];
char S[N],s[N<<1];
il int read()
{
    rg int s=0,m=0;rg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
il void change()
{
    s[0]=s[1]='#';
    for(rg int i=0;i<n;++i)
    {
        s[(i<<1)+2]=S[i];
        s[(i<<1)+3]='#';
    }
    s[n=(n<<1)+2]=0;
}
il void manacher()
{
    rg int mx=0,id;
    for(rg int i=1;i<n;++i)
    {
        if(i<mx)p[i]=min(p[(id<<1)-i],mx-i);
        else p[i]=1;
        while(s[i+p[i]]==s[i-p[i]])p[i]++;
        if(p[i]+i>mx)
            mx=p[i]+i,id=i;
    }
}
int main()
{
    cin>>S;
    n=strlen(S);
    change();
    manacher();
    for(rg int i=0;i<n;++i)
        ans=max(ans,p[i]);
    printf("%d\n",ans-1);
    return 0;
}

题单(xzy，都是xzy的没错)

• [luogu3805]【模板】manacher算法 https://www.luogu.org/problemnew/show/P3805
• [BZOJ3790]神奇项链 http://172.40.25.127:5283/problem/113790
• [SHOI2011]双倍回文 https://www.luogu.org/problemnew/show/P4287
• [ZJOI2009]对称的正方形 https://www.luogu.org/problemnew/show/P2601
• [luogu1659][国家集训队]拉拉队排练 https://www.luogu.org/problemnew/show/P1659
• [luogu4555]最长双回文串 https://www.luogu.org/problemnew/show/P4555
• [BZOJ3160]万径人踪灭 https://www.luogu.org/problemnew/show/P4199