hdu3068 最长回文--Manacher算法
发布日期:2021-10-03 20:31:49
浏览次数:3
分类:技术文章
本文共 1201 字,大约阅读时间需要 4 分钟。
原题链接:
一:原题内容
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
aaaaabab
Sample Output
43
二:分析理解
参见:
三:AC代码
#include#include #include #include using namespace std;char s[110010];char s_new[220020];int p[220020];int Init(){ int len = strlen(s); s_new[0] = '$'; s_new[1] = '#'; int j = 2; for (int i = 0; i < len; i++) { s_new[j++] = s[i]; s_new[j++] = '#'; } s_new[j] = '\0';//别忘了哦 return j;//返回s_new的长度}int Manacher(){ int len = Init();//取得新字符串长度并完成向s_new的转换 int maxLen = -1;//最长回文长度 int id; int mx = 0; for (int i = 1; i < len; i++) { if (i < mx) p[i] = min(p[2 * id - i], mx - i);//需搞清楚上面那张图含义,mx,2 * id - i的含义 else p[i] = 1; while (s_new[i - p[i]] == s_new[i + p[i]])//不需边界判断,因为左有'$',右有'\0' p[i]++; if (mx < i + p[i])//我们每走一步i,都要和mx比较,我们希望mx尽可能的远,这样才能更有机会执行if (i < mx) 这句代码,从而提高效率 { id = i; mx = i + p[i]; } maxLen = max(maxLen, p[i] - 1); } return maxLen;}int main(){ while (scanf("%s", s)==1) printf("%d\n", Manacher()); return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50932904 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月13日 15时41分05秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
hashCode到底有什么用?
2019-04-28
设计模式之动态代理模式实战
2019-04-28
设计模式之静态代理模式实战
2019-04-28
作为架构师,你必需要搞清楚的概念:POJO、PO、DTO、DAO、BO、VO
2019-04-28
mysql查询优化explain命令详解
2019-04-28
常用加密算法解析
2019-04-28
设计模式之单例模式实践
2019-04-28
彻底理解正向代理和反向代理
2019-04-28
一次频繁Full GC的排查过程,根源居然是它...
2019-04-28
【爬虫】简单十行代码爬取B站的B站弹幕
2019-04-28
Servlet 体系结构
2019-04-28
Java笔记—语法
2019-04-28
Java笔记—数组
2019-04-28
Java笔记—继承
2019-04-28
MySQL的数据类型
2019-04-28
洛谷 P1886 滑动窗口 /【模板】单调队列
2019-04-28
洛谷 P3367 【模板】并查集
2019-04-28
【算法学习】高级数据结构2 种类并查集
2019-04-28
洛谷 P1525 关押罪犯【种类并查集】
2019-04-28
洛谷 P2024 [NOI2001]食物链【种类并查集】
2019-04-28