NOIP 冲刺之manacher模板
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
char a[22000009];
int len,mx;
int p[22000009];
int ans=0;
int id;
int main(){
    scanf("%s",a);
    len=strlen(a);
    for(int i=len-1;i>=0;--i){
        a[i*2+2]=a[i];
        a[i*2+3]='$';
    }
    a[0]='#';    
    a[1]='$';  
    a[len*2+2]='@';
    len=len*2+2;
    mx=0;
    for(int i=0;i<len;i++){
       if(i<mx) p[i]=min(mx-i,p[2*id-i]);
       else p[i]=1;
       while(a[i+p[i]]==a[i-p[i]])
                ++p[i];
        if(i+p[i]>mx){
            mx=i+p[i];
            id=i;
        }
       ans=max(ans,p[i]);
    }   
    printf("%d",ans-1);
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议