最长回文

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068

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 <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int N = ;
char s[N],tmp[N];;
int p[N];
void Manacher(char *s){
memset(p,,sizeof(p));
int l=strlen(s);
strcpy(tmp,s);
s[]='$';
for(int i=;i<=*l+;i++){
if(i&) s[i]='#';
else s[i]=tmp[i/-];
}
s[*l+]='\0';
int mx=,id=;
l=strlen(s);
for(int i=;i<l;i++){
if(i>=mx) p[i]=;
else p[i]=min(mx-i,p[*id-i]);
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(p[i]+i>mx){
mx=p[i]+i;
id=i;
}
}
}
int main(){
while(scanf("%s",s)!=EOF){
Manacher(s);
int ans = ;
int l=strlen(s);
for(int i=;i<l;i++) ans=max(ans,p[i]-);
printf("%d\n",ans);
}
return ;
}

最新文章

  1. VS2015链接错误一则
  2. poj 2515 差分序列,排列组合
  3. Servlet中转发和重定向的区别
  4. nginx学习(2):启动gzip、虚拟主机、请求转发、负载均衡
  5. AutoLayout 图解各种约束
  6. mysql多种方法修改密码----5.6的坑
  7. poj 1742 Coins (多重背包)
  8. Apache-系统-网络部分配置
  9. HDU 1708
  10. 自由缩放属性-resize(禁止textarea的自由缩放尺寸功能)
  11. Xcode8注释有时会失效的解决方法
  12. 20175211 2018-2019-2 《Java程序设计》第六周学习总结
  13. skynet记录2:模块简介
  14. 洛谷 P1879 玉米田(状压DP入门题)
  15. vmware中如何检查cpu的使用状况-一个考题引发的思考
  16. find 命令 查找
  17. Mybatis中映射器实现方式总结
  18. Spring Boot集成持久化Quartz定时任务管理和界面展示
  19. Asp.Net发送手机验证码
  20. python基础学习1-迭代器

热门文章

  1. [CodeForce721C]Journey
  2. dice2win
  3. [leetcode-676-Implement Magic Dictionary]
  4. iscroll手册
  5. 【转】Expressions versus statements in JavaScript
  6. 无法启动mysql服务 错误1067:进程意外中止
  7. JAVA mysql数据库 配置
  8. catalan卡塔兰数
  9. 展示github中的页面(Github Pages)
  10. 使用cookies模拟登陆