洛谷 P3805 【模板】manacher算法

洛谷 P3805 【模板】manacher算法

洛谷传送门

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入格式

一行小写英文字符a,b,c...y,z组成的字符串S

输出格式

一个整数表示答案

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

字符串长度len <= 11000000

题解：

都说了是(Manacher)算法的模板了...

关于马拉车算法，如有不懂请参考本蒟蒻的这篇博客：

详解Manacher算法

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxl=51000100;
char a[maxl];
int rad[maxl];
char s[maxl<<1];
int len,ans=1;
void init()
{
    s[0]=s[1]='#';
    for(int i=0;i<len;i++)
    {
        s[i*2+2]=a[i];
        s[i*2+3]='#';
    }
    len=len*2+2;
    s[len]=0;
}
void manacher()
{
    int mr=0,mid;
    for(int i=1;i<len;i++)
    {
        if(i<mr)
            rad[i]=min(rad[(mid<<1)-i],rad[mid]+mid-i);
        else
            rad[i]=1;
        for(;s[i+rad[i]]==s[i-rad[i]];rad[i]++)
            if(i+rad[i]>mr)
            {
                mr=i+rad[i];
                mid=i;
            }
    }
}
int main()
{
    scanf("%s",a);
    len=strlen(a);
    init();
    manacher();
    for(int i=0;i<len;i++)
        ans=max(ans,rad[i]);
    printf("%d
",ans-1);
    return 0;
}