最长回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 31611    Accepted Submission(s): 11618

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 <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
//最长回文,Manacher算法
char s[],c[];//注意S数组的大小至少要开C数组的两倍
int p[];//P可以理解为回文字符串的半径 void init()//初始化S数组
{
int i,j;
s[]='@';
for(i=;c[i]!=;i++)
{
s[*i+]='#';
s[*i+]=c[i];
}
s[*i+]='#';
s[*i+]=;
}
int manacher()
{
int id=,mx=,i;
for(i=;s[i]!=;i++)
{
if(mx>i)
p[i]=min(p[*id-i],mx-i);
else
p[i]=;
//p[i]=mx>i?min(p[2*id-i],mx-i):1;
while(s[i+p[i]] == s[i-p[i]])
p[i]++;
if(i+p[i]>mx)
{
mx=i+p[i];
id=i;
}
}
mx=;
for(i=;s[i]!=;i++)
{
if(p[i]>mx)
mx=p[i];
}
return mx-;
}
int main()//用cin\cout 会超时
{
while(~scanf("%s",c))
{
init();
printf("%d\n",manacher());
}
return ;
}

最新文章

  1. iOS cocoapods升级及问题
  2. 如何删除datatable中的一行数据
  3. python之sys模块详解
  4. 【人在江湖飘,哪有不带刀】神器Jumony
  5. Android——AnimationDrawable 实现动画
  6. zhuan:点滴记录——Ubuntu 14.04中gedit打开文件出现中文乱码问题
  7. 【转】android:DDMS查看Threads--不错
  8. Jmeter新建用例图示
  9. UPUPW配置
  10. java面向对象编程(七)--四大特征之多态
  11. OVS常用命令与使用总结
  12. WIN7虚拟桌面创建(多屏幕多桌面)
  13. Arrow模块生成时间
  14. 离线安装Cloudera Manager 5和CDH5(最新版5.9.3) 完全教程(四)数据库安装(单节点)
  15. iOS开发之--解决 swap file “*.swp”already exists!问题
  16. C# 如何批量修改集合元素的属性值?
  17. python基础学习Day11 函数名的应用、闭包、迭代器
  18. 【Unity】UGUI系列教程——拼接一个简单界面
  19. MapReduce的洗牌(Shuffle)
  20. Java 架构师

热门文章

  1. cocos2d-js 浏览器与JSB内存管理机制的不同
  2. 05 HTML字符串转换成jQuery对象、绑定数据到元素上
  3. Qt中显示图像的两种方法
  4. CF 464E The Classic Problem
  5. Luogu 3479 [POI2009]GAS-Fire Extinguishers
  6. Luogu 4323 [JSOI2016]独特的树叶
  7. C和C++中文件读写的区别
  8. C++笔记--指针数组和结构
  9. 《Head First Servlets & JSP》-10-定制标记开发
  10. Spring Bean的装配