hdu3068 求一个字符串中最长回文字符串的长度 Manacher算法
2024-10-20 01:28:14
最长回文
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
两组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 ;
}
最新文章
- iOS cocoapods升级及问题
- 如何删除datatable中的一行数据
- python之sys模块详解
- 【人在江湖飘,哪有不带刀】神器Jumony
- Android——AnimationDrawable 实现动画
- zhuan:点滴记录——Ubuntu 14.04中gedit打开文件出现中文乱码问题
- 【转】android:DDMS查看Threads--不错
- Jmeter新建用例图示
- UPUPW配置
- java面向对象编程(七)--四大特征之多态
- OVS常用命令与使用总结
- WIN7虚拟桌面创建(多屏幕多桌面)
- Arrow模块生成时间
- 离线安装Cloudera Manager 5和CDH5(最新版5.9.3) 完全教程(四)数据库安装(单节点)
- iOS开发之--解决 swap file “*.swp”already exists!问题
- C# 如何批量修改集合元素的属性值?
- python基础学习Day11 函数名的应用、闭包、迭代器
- 【Unity】UGUI系列教程——拼接一个简单界面
- MapReduce的洗牌(Shuffle)
- Java 架构师