1. 题目

传送门= ̄ω ̄=

题意:给你几个字符串,问每个字符串内最长回文子串的长度。要用$O(n)$的算法。

2. 题解

manacher(马拉车)算法模板题。

对于manacher我推荐一个视频吧(我在B站学算法QvQ):UESTCACM 每周算法讲堂 manacher算法

代码:

#include <bits/stdc++.h>
#define NS (300000)
using namespace std;
char s[NS],str[NS];
int len1,len2,p[NS],ans;
void init()
{
    len2=(len1<<1)+2,str[0]='$',str[1]='#',str[len2]='\0';
    for(int i=0;i<len1;i++)str[(i<<1)+2]=s[i],str[(i<<1)+3]='#';
}
void manacher()
{
    int id=0,mx=0;
    for(int i=1;i<len2;i++)
    {
        if(mx>i)p[i]=min(p[(id<<1)-i],mx-i);
        else p[i]=1;
        while(str[i-p[i]]==str[i+p[i]])p[i]++;
        if(i+p[i]>mx)id=i,mx=i+p[i];
    }
}
int main()
{
    while(~scanf("%s",s))
    {
        len1=strlen(s),init(),manacher(),ans=0;
        for(int i=1;i<len2;i++)ans=max(ans,p[i]);
        printf("%d\n",ans-1);
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *