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