Manacher算法

Luogu P3805 【模板】manacher算法

初学 $ Manacher $ (马拉车)算法
Manacher算法用于处理回文串问题,可以求出每个字符所在的最长回文串的长度

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=11000005;
char s[N],sw[2*N];
int r[2*N];
int deal()
{
    int len=strlen(s);
    sw[0]='$';
    sw[1]='#';
    int lon=2;
    for(int i=0;i<len;i++)
    {
        sw[lon++]=s[i];
        sw[lon++]='#';
    }
    sw[lon]='\0';
    return lon;
}
int manacher()
{
    int len=deal();
    int id,mx=0,maxlon=0;
    for(int i=1;i<len;i++)
    {
        if(i>=mx) r[i]=1;
        else r[i]=min(r[2*id-i],mx-i);
        while(sw[i-r[i]]==sw[i+r[i]]) r[i]++;
        if(mx<i+r[i])
        {
            id=i;
            mx=i+r[i];
        }
        maxlon=max(maxlon,r[i]-1);
    }
    return maxlon;
}
int main()
{
    cin>>s;
    printf("%d\n",manacher());
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。