题解 | #回文串#manacher

本题的样例有点水了
第一次提交的代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=1400;
char a[N];
char manacher[N<<1];
int p[N<<1];
int main()
{
    while(scanf("%s",a)!=EOF){
        memset(p,0,sizeof p);
        memset(manacher,0,sizeof manacher);
        int T=0;
        int n=strlen(a);
        for(int i=0;i<n;i++){
            manacher[T++]='#';
            manacher[T++]=a[i];
        }
        manacher[T++]='#';  //初始化数组
        int maxid=0;
        int id=0;
        int ans=0;
        for(int i=0;i<T;i++){
            if(maxid>i){
                p[i]=min(maxid-i,p[id*2-i]);
            }
            else{
                p[i]=1;

            }
            while(manacher[i-p[i]]==manacher[i+p[i]]) p[i]++;
            if(i+p[i]>maxid){
                maxid=i+p[i];
                id=i;
            }
            ans=max(ans,p[i]-1);
        } 
        cout<<ans<<"\n";
    }
}

如果开始输入的就是回文串，则该代码无法正确输出，因为while循环会一直运行
后来在while循环那里加了一个判断 如果p[i]+i>字符串总长度时直接结束循环，可以得到正确的答案

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=1400;
char a[N];
char manacher[N<<1];
int p[N<<1];
int main()
{
    while(scanf("%s",a)!=EOF){
        memset(p,0,sizeof p);
        memset(manacher,0,sizeof manacher);
        int T=0;
        int n=strlen(a);
        for(int i=0;i<n;i++){
            manacher[T++]='#';
            manacher[T++]=a[i];
        }
        manacher[T++]='#';  //初始化数组
        int maxid=0;
        int id=0;
        int ans=0;
        for(int i=0;i<T;i++){
            if(maxid>i){
                p[i]=min(maxid-i,p[id*2-i]);
            }
            else{
                p[i]=1;

            }
            while(manacher[i-p[i]]==manacher[i+p[i]])
            {
                if(i+p[i]>=T){
                    break;
                }
                p[i]++;
             } 
            if(i+p[i]>maxid){
                maxid=i+p[i];
                id=i;
            }
            ans=max(ans,p[i]-1);
        } 
        cout<<ans<<"\n";
    }
}