【BZOJ 2565】 最长双回文串
2024-09-01 22:21:33
【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=2565
【算法】
Manacher
【代码】
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ; char s[MAXN]; inline void Manacher()
{
int i,pos = ,mx = ,len,ans = ;
static char tmp[MAXN<<];
static int p[MAXN<<],l[MAXN<<],r[MAXN<<];
len = strlen(s+);
for (i = ; i <= len; i++)
{
tmp[*i-] = '#';
tmp[*i] = s[i];
}
tmp[len = * len + ] = '#';
for (i = ; i <= len; i++)
{
if (mx > i) p[i] = min(p[*pos-i],mx-i);
else p[i] = ;
while (i - p[i] >= && i + p[i] <= len && tmp[i-p[i]] == tmp[i+p[i]]) p[i]++;
if (i + p[i] - > mx)
{
mx = i + p[i] - ;
pos = i;
}
}
pos = ;
for (i = ; i <= len; i++)
{
if (tmp[i] == '#')
{
while (pos + p[pos] < i) pos++;
l[i] = i - pos;
}
}
pos = len;
for (i = len; i >= ; i--)
{
if (tmp[i] == '#')
{
while (pos - p[pos] > i) pos--;
r[i] = pos - i;
}
}
for (i = ; i <= len; i++) ans = max(ans,l[i]+r[i]);
printf("%d\n",ans);
} int main()
{ scanf("%s",s+);
Manacher(); return ; }
最新文章
- 转载文章——从HelloWorld学习操作系统
- ZOJ 3703 Happy Programming Contest
- 错误-spring3.2的架构在tomcat6.0中无法正常启动,抛出java.lang.NoClassDefFoundError: javax/servlet/AsyncListener
- TypeError: &#39;bases&#39; is null or not an object。IE8 bug 腐朽的对象
- C# 根据包含文件的路径和文件的名称的字符串获取文件名称的几种方法
- Microsoft Dynamics CRM 2013 CD-KEY
- [CentOS]yum安装postgres和ntfs-3g
- CSS3--幽灵按钮特效(实例)
- 人工智能起步-反向回馈神经网路算法(BP算法)
- 汽车行业的DMS系统 IT不变应万变
- Geogebra里给带有曲线和直线混合边界的封闭区域填充颜色
- shell 验证ip
- windows server 2008 应用程序池自动关闭 C:\Windows\system32\RpcProxy\RpcProxy.dll failed to load
- 201521123111《Java程序设计》第10周学习总结
- python3抓图学习-百度贴吧
- 配置STP、RSTP以及负载均衡
- xcodebuild构建时报错unknown error -1=ffffffffffffffff Command /bin/sh failed with exit code 1
- 【知名的移动APP和网站设计工具】Sketch for Mac 54.1
- [C]内存管理、内存泄露、堆栈
- 06 - JavaSE之常用类