Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S,两组case之间由空行隔开(该空行不用处理),字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4

3

#include<cstdio>
#include<iostream>
#include<cstring>
#define M 220010
using namespace std;
char s,s1[M],s2[M];
int n,p[M];
void manacher()
{
int id=,mx=,ans=;
for(int i=;i<=*n;i++)
{
if(mx>i)p[i]=min(p[*id-i],mx-i);
else p[i]=;
while(s2[i+p[i]]==s2[i-p[i]])++p[i];
if(i+p[i]>mx)
{
id=i;
mx=i+p[i];
}
ans=max(ans,p[i]-);
}
printf("%d\n",ans);
}
void init()
{
n=strlen(s1);
s2[]='$';
for(int i=;i<=n;i++)
s2[*i+]='#',s2[*i+]=s1[i];
manacher();
}
int main()
{
while(scanf("%s",s1)!=EOF)
{
memset(p,,sizeof(p));
memset(s2,,sizeof(s2));
init();
}
return ;
}

最新文章

  1. Codeforces663E Binary Table(FWT)
  2. 大学站防SQL注入代码(ASP版)
  3. POJ 2948 Martian Mining
  4. 自定义C/C++头文件以及头文件重复定义解决
  5. 语义化HTML
  6. SQL 查询45题
  7. 分布式文件系统FastDFS原理介绍
  8. Nginx Rewrite 实现匹配泛域名规则
  9. Zabbix Api的使用
  10. Android单元测试初探——Instrumentation(转载)
  11. PHP PSR-4 Autoloader 自动加载(中文版)
  12. windows composer安装
  13. underscore.js中的节流函数debounce及trottle
  14. Android开发学习之路--基于vitamio的视频播放器(二)
  15. Flask 之东方不败一
  16. 【Linux】阿里云ECS提示RHSA-2017:3263: curl security update(CentOS 7 更新 curl 为最新版本)
  17. oracle安装教程
  18. UEditor (富文本编译器)
  19. 约瑟夫环(Joseph)的高级版(面向事件及“伪链表””)
  20. 自制数据结构(容器)-java开发用的最多的ArrayList和HashMap

热门文章

  1. Java并发——结合CountDownLatch源码、Semaphore源码及ReentrantLock源码来看AQS原理
  2. ES6学习笔记(10)----Set和Map数据结构
  3. android 代码中及xml中设置透明
  4. 在Vue中遇到的各种坑 及性能提升
  5. 微信小程序---代码构成
  6. day09 10 11 12 三天函数内容
  7. vue在传值的时候经常遇到的问题
  8. SMTP error 554 !!
  9. Rust所有权语义模型
  10. 【练习】reserving.kr 之imageprc write up