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