洛谷 P3805 【模板】manacher算法
2023-09-11 14:20:16 时间
洛谷 P3805 【模板】manacher算法
题目描述
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
字符串长度为n
输入格式
一行小写英文字符a,b,c...y,z组成的字符串S
输出格式
一个整数表示答案
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
字符串长度len <= 11000000
题解:
都说了是\(Manacher\)算法的模板了...
关于马拉车算法,如有不懂请参考本蒟蒻的这篇博客:
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxl=51000100;
char a[maxl];
int rad[maxl];
char s[maxl<<1];
int len,ans=1;
void init()
{
s[0]=s[1]='#';
for(int i=0;i<len;i++)
{
s[i*2+2]=a[i];
s[i*2+3]='#';
}
len=len*2+2;
s[len]=0;
}
void manacher()
{
int mr=0,mid;
for(int i=1;i<len;i++)
{
if(i<mr)
rad[i]=min(rad[(mid<<1)-i],rad[mid]+mid-i);
else
rad[i]=1;
for(;s[i+rad[i]]==s[i-rad[i]];rad[i]++)
if(i+rad[i]>mr)
{
mr=i+rad[i];
mid=i;
}
}
}
int main()
{
scanf("%s",a);
len=strlen(a);
init();
manacher();
for(int i=0;i<len;i++)
ans=max(ans,rad[i]);
printf("%d\n",ans-1);
return 0;
}
相关文章
- 第二百五十八节,Tornado框架-逻辑处理get()方法和post()方法,初识模板语言
- django模板语言的注释
- flask框架-模板语言Jinja
- eclipse常用功能:代码重构(变量批量重命名)、自定义注释、代码模板、打开断言
- c++模板学习08之类模板与继承
- Atitit 字符串模板与 字符串插值 目录 1.1. 字符串插值是将字符串中的占位符替换为局域变量的过程1 1.2. 模板字面量 是允许嵌入表达式的字符串字面量1 1.3. 格式化字符串[编辑
- Atitit opencv 模板匹配
- 填充数据到word模板中
- 习题 9.12 将例9.14改写为在类模板外定义各成员函数。
- JavaScript学习总结(二)——延迟对象、跨域、模板引擎、弹出层、AJAX示例
- ubuntu20.04/16.04下C++的通用Makefile模板解析
- Idea设置类注释模板
- 动态规划 背包问题算法模板 0-1背包 0-1带价值背包 多重背包问题
- 堆栈算法模板
- Tire 字典树模板和算法总结
- 双指针算法模板题目
- 【算法竞赛刷题模板15】【二维数组前缀和】
- 【算法竞赛刷题模板12】单调队列
- springboot使用jxls导出excel___(万能通用模板)--- SpringBoot导入、导出Excel文件___SpringBoot整合EasyExcel模板导出Excel
- 【跟学C++】C++STL标准模板库——算法详细整理(下)(Study18)