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;
}