自动搬运

查看原文

来自洛谷，原作者为

	三好代表 奈何桥上手执花，皎洁明月照满家；屋内倩影轻似笑，细雨微微荡天涯

搬运于2025-08-24 21:28:20，当前版本为作者最后更新于2019-03-30 16:02:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要说一下思路，我们先复制一遍模板（甚至变量都不用改

然后唯一的区别就是要求的是最长连续回文子串长度

那么我们就在Manacher函数里在最后统计一下最大值就行

优秀的代码在这里

#include<bits/stdc++.h>
using namespace std;
const int N = 21000000;
char s[N],str[N];
int p[N],n;
int init(){
    int len=strlen(s);
    str[0]='@',str[1]='#';
    int j=1;
    for(int i=0;i<len;++i){
        str[++j]=s[i];
        str[++j]='#';
    }
    str[++j]='\0';
    return j;
}
int Manacher(){
    int id=1,mx=1,maxn=0,len=init();
    for(int i=1;i<len;++i){
        if(i<mx) p[i]=min(p[id*2-i],mx-i);
        else p[i]=1;
        while(str[i-p[i]]==str[i+p[i]]) p[i]++;
        if(i+p[i]>mx){
            mx=i+p[i];
            id=i;
        }
        maxn=max(maxn,p[i]-1);//敲黑板，唯一的区别
    }
    return maxn;
}
int main(){
    cin>>n;
    while(n--){
        memset(p,0,sizeof(p));
        cin>>s;
        cout<<Manacher()<<endl;
    }
    return 0;
}