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
 
Source
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  1358 3336 3065 3746 1711 
 

manachar讲解:   http://blog.csdn.net/bruce_zeng/article/details/8629572

代码:

 #include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
#define N 110010*2 char s[N],str[N];
int p[N]; int init()
{
int i,j=;
str[j++]='$';
for(i=;s[i];i++){
str[j++]='#';
str[j++]=s[i];
}
str[j++]='#';
str[j]='\0';
return j;
} void manachar(int n)
{
int mx=,id,i;
p[]=;
for(i=;i<n;i++){
if(mx>i)
p[i]=min(mx-i,p[*id-i]);
else
p[i]=;
while(str[i-p[i]]==str[i+p[i]])
p[i]++;
if(p[i]+i>mx){
mx=p[i]+i;
id=i;
}
}
} int main()
{
int n;
while(~scanf("%s",s)){
n=init();
manachar(n);
int ans=;
for(int i=;i<n; i++){
if(p[i]>ans)
ans=p[i];
}
printf("%d\n",ans-);
}
}

最新文章

  1. 关于svg格式图片颜色更改
  2. hdu 1251 统计难题 (字典树入门题)
  3. TCPDF 6.0.036 发布,PHP 的 PDF 操作包
  4. Linq查询操作之聚合操作(count,max,min,sum,average,aggregate,longcount)
  5. javascript Date format(js日期格式化)
  6. 每天一个linux命令(24):gzip命令
  7. Java控制语句——for循环
  8. windows下 破解 Sublime Text3 和汉化
  9. 配置CAS错误No Certificate file specified or invalid file format
  10. shopnc 发票项目
  11. Swift - 标签条(UITabBar)标签页控制器(UITabBarController)用法
  12. Form表单提交,Ajax请求,$http请求的区别
  13. mysql-笔记-类型转化
  14. 使用styled-components实现CSS in JS
  15. CSS3 选择器 基本选择器介绍
  16. JSON和Serialize数据格式的对比
  17. Loading AssetBundle Manifests
  18. CSS一个元素同时使用多个类选择器(class selector)
  19. git添加公钥后报错sign_and_send_pubkey: signing failed: agent refused operation
  20. 关于HBase Shell命令基本操作示例

热门文章

  1. 数据结构读书笔记(二)(C语言)
  2. WPF 3D:使用变换中的TranslateTransform3D
  3. 【原创】只学到二维数组和结构体,不用链表也能写一个C贪食蛇?(四)
  4. POJ 2538 WERTYU水的问题
  5. mtk硬件项目开始关闭蓝牙功能:mtk 硬件ScanCode和keycode应用演示示例
  6. hdu1325 Is It A Tree?并检查集合
  7. Oracle游标(光标)
  8. JAVA Metrics 度量工具使用介绍1
  9. 用正交多项式作最小二乘拟合的java实现(转)
  10. Freedur为什么免费?