【模板】manacher算法
2024-08-31 22:01:07
#include <cstdio>
#include <cstring>
#define N 22200000
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) int p[N];
char s[N];
int pos = 1, maxright, ans, n; int main()
{
int i, j;
scanf("%s", s + 1);
n = strlen(s + 1);
s[0] = '$', s[n * 2 + 1] = '#';
for(i = n; i >= 1; i--) s[i * 2] = s[i], s[i * 2 - 1] = '#';
n = n * 2;
for(i = 1; i <= n; i++)
{
p[i] = 1;
if(i <= maxright)
p[i] = min(p[pos * 2 - i], maxright - i + 1);
while(s[i - p[i]] == s[i + p[i]]) p[i]++;
if(maxright < i + p[i] - 1)
{
pos = i;
maxright = i + p[i] - 1;
}
ans = max(ans, p[i] - 1);
}
printf("%d\n", ans);
return 0;
}
最新文章
- CCNA网络工程师学习进程(1)网络的基本概述
- Android - ADB 的使用
- 彻底弄明白之java多线程中的volatile
- SpringMVC从Controller跳转到另一个Controller
- web页面隐藏鼠标
- 千万级SQL Server数据库表分区的实现
- CAS 单点登录流程
- 【风马一族_Python】 更替pip的版本
- TeeChart的X轴为时间,多个Y轴的显示
- [LeetCode]题解(python):025-Reverse Nodes in k-Group
- C++11 virtual函数学习笔记
- shell之crontab
- [图形学] Chp9 三维几何变换--栈处理函数与矩阵管理函数的区别
- Spring ioc与aop的理解
- Linux系统下安装JDK
- Spring Boot SSL
- WebAPI参数传值string转bool,int转bool相关问题
- C++:__stdcall详解
- 20145325张梓靖 《网络对抗技术》 Web安全基础实践
- git工具学习
热门文章
- [转]List of Visual Studio Project Type GUIDs
- JavaScript禁止键入非法值,只有这些才能被键入
- 通过流传入excel解析的问题
- Maven项目中War包的打包及依赖方式
- How to proxy a web site by apache2 in Ubuntu
- php中session实现机制
- 年度精品 XP,32/64位Win7,32/64位Win10系统【电脑城版】
- SAS Fuctions
- H3C S5024P交换机 H3C AR28-31路由器命令
- dirname, basename - 分析路径成员