回文串的Manacher算法
2024-10-08 22:17:35
Manacher算法较传统算法的优化之处在于它对每个回文中心寻找回文半径的时候并不是都从半径为1开始找的,而是利用前面已经完成的任务,寻找一个初始的开始搜索的半径大小,复杂度是线性的。
参考博客:https://www.cnblogs.com/z360/p/6375514.html
下面附上hdoj的3068模板:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
#define maxn 110005
int n,m,t;
char s[maxn];
char tmp[maxn<<];
int l[maxn<<];//转换后的字符串以及最大回文半径
int manacher(char *st,int len)
{
int t=;
tmp[t++]='$';
tmp[t++]='#';
f(i,,len-)
{
tmp[t++]=s[i];
tmp[t++]='#';
}
tmp[t]=;
int mr=,ans=,pos=;//最长回文右端、最长回文长度以及回文中心
f(i,,t-)
{
l[i]=mr>i?min(mr-i,l[*pos-i]):;
//i>=mr时需要以i为新的回文中心开始搜索回文长度
while(tmp[i-l[i]]==tmp[i+l[i]])l[i]++;
if(i+l[i]>mr)//更新最大回文右端点
{
mr=i+l[i];
pos=i;
}
ans=max(ans,l[i]);
}
return ans-;//每次回文串长度为2*k+1时,多余字符为k+1个,有k个属于原串的字符
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%s",s)!=EOF)
{
int len=strlen(s);
pf("%d\n",manacher(tmp,len));
} }
最新文章
- sql语句,怎么取查询结果的位置
- JSPatch 中 defineClass 中覆盖方法的使用
- 记录s标签范例
- parameter和argument的区别
- 在ubuntu 10.04下编译ffmpeg
- android 在布局中动态添加控件
- 第四篇、Tomcat 集群
- (step4.3.1) hdu 1010(Tempter of the Bone——DFS)
- oracle ebs 12.20 安装成功其过程失败日记及总结(1)
- 如何实现MySQL随机查询数据与MySQL随机更新数据?
- java war 打包、解压命令
- -linux删除大量文件----rm,rsync
- 基于python的知乎开源爬虫 zhihu_oauth使用介绍
- Android ble蓝牙问题
- 记录一次配置golang服务器端口
- AHB总线协议
- sql注入总结(一)--2018自我整理
- oracle sql 添加、修改数据库操作方式
- 深入php内核,从底层c语言剖析php实现原理
- git报错:Pull is not possible because you have unmerged files解决方法