BZOJ2565: 最长双回文串(Manacher)
2024-09-08 02:49:59
Description
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
Input
一行由小写英文字母组成的字符串S。
Output
一行一个整数,表示最长双回文子串的长度。
Sample Input
baacaabbacabb
Sample Output
12
解题思路:
是求两个回文串相加的双回文最大长度。
一直在想两个回文串相交的情况,结果发现是不存在的,那样只会形成更大的一个回文串,蒟蒻就是蒟蒻
记录最右点和最左点。
注意更新!!
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
char a[];
int l[];
int ls[];
int rs[];
int f[];
int ans;
int cnt;
int main()
{
scanf("%s",a+);
int len=strlen(a+);
l[cnt]='&';
for(int i=;i<=len;i++)
{
l[++cnt]='&';
l[++cnt]=a[i];
}
l[++cnt]='&';
int mx=;
f[]=;
for(int i=;i<=cnt;i++)
{
f[i]=min(f[mx*-i],f[mx]+mx-i);
while(f[i]+i<=cnt&&l[f[i]+i]==l[i-f[i]])
f[i]++;
if(mx+f[mx]<i+f[i])
mx=i;
rs[f[i]+i-]=max(rs[f[i]+i-],f[i]-);
ls[i-f[i]+]=max(ls[i-f[i]+],f[i]-);
}
for(int i=;i<=cnt;i+=)
ls[i]=max(ls[i],ls[i-]-);
for(int i=cnt;i>=;i-=)
rs[i]=max(rs[i],rs[i+]-);
for(int i=;i<=cnt;i+=)
ans=max(ans,rs[i]+ls[i]);
printf("%d\n",ans);
return ;
}
最新文章
- 设计模式(十):从电影院中认识";迭代器模式";(Iterator Pattern)
- 原创jquery插件treeTable(转)
- WinForm------DockManager控件的使用方法(里面包含DockPanel控件)
- js解析php数组
- linux总线、设备和设备驱动的关系
- Oracle EBS-SQL (INV-2):检查帐户别名发放记录.sql
- 替换 window.location当中的某个参数的值(而其它值不变)JS代码
- IMP-00013 目前只有 DBA 其他导入能力 DBA 导出的文件
- js基于谷歌地图API绘制可编辑圆形与多边形
- Java 到底是值传递还是引用传递
- 使用freemarker模板引擎生成word文档的开发步骤
- 二叉树的Python实现
- Android BLE蓝牙详细解读
- springboot系列之-logging
- 总结&;#183;展望
- 数据库使用:sql server/mysql/sqlite
- Mongo读书笔记2 -- 数据类型
- Wacom将在CES 2015上发布全新旗舰版Cintiq
- [Violet]天使玩偶
- Robot Framework Change chrome language
热门文章
- DOM基础及DOM操作HTML
- CSS3绘制砖墙-没实用不论什么图片
- UVA 12716 GCD XOR(数论+枚举+打表)
- 理解FPGA中的RAM、ROM和CAM;ROM、RAM、DRAM、SRAM、FLASH
- 智课雅思词汇---七、cur是什么意思
- BZOJ 3224 平衡树模板题
- Gym - 100625J Jailbreak 最短路+搜索
- 今日SGU 5.23
- PAT-中国大学MOOC-陈越、何钦铭-数据结构基础习题集 00-自測4. Have Fun with Numbers (20) 【二星级】
- js02---字符串