manacher 算法
2022/9/17 1:17:24
本文主要是介绍manacher 算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
回文串
回文串是正着读和反着读都一样的字符串。
例如: abcba,noon。
manacher 算法就是用来求解一个字符串中最大回文串的长度。
算法过程
1.预处理
由于回文串分为偶回文串和奇回文串,这导致一个回文串的对称中心可能是一个也可能是两个,不方便处理。
abcba 的对称中心是c
noon 的对称中心是oo
所以我们可以在初始字符串的每个字符之间插入特殊字符(只要该字符不出现在原字符串即可)
noon 插入\(\$\),变为\(\$n\$o\$o\$n\$\)
插入之后回文性质没有改变,并且所有的回文串都变成了奇回文串,方便我们进行后续操作。
2.manacher 算法主体
定义数组p[i]表示以第i个字符为对称中心的最长回文串的半径,那么p[i]-1就是以第i个字符为对称中心的回文串长度(因为要去除插入的字符$)
用mx表示目前找到的回文串最右端的位置,该回文串的中心用mid表示
看上面这张图,我们要求p[i],j为i关于mid的对称点,而且我们已知p[j],那么就有
p[i]=min(mx-i,p[j])
这是因为在mx左边的部分可以用p[j]确定p[i]的长度,因为他们是关于mid对称的也就是完全一样的。
但是右边的部分不能保证,要用暴力法判断。
时间复杂度O(n)
详细请看代码
例题P3805 【模板】manacher 算法
#include<bits/stdc++.h> using namespace std; const int N=1.1e7+10; char a[2*N],s[2*N]; int p[2*N]; int n; int cnt=0; void change(){ s[cnt++]='^';//这个东西防止越界 s[cnt++]='$'; for(int i=0;i<n;++i)s[cnt++]=a[i],s[cnt++]='$'; } int manacher(){ int mx=0,mid=0,ans=0; for(int i=0;i<cnt;++i){ if(i<mx)p[i]=min(mx-i,p[mid*2-i]); else p[i]=1; while(s[i+p[i]]==s[i-p[i]])p[i]++;//暴力判断右边的部分 if(mx<i+p[i])mx=i+p[i],mid=i;//更新右边界 //ans=max(ans,p[i]-1); if(ans<p[i]-1)ans=p[i]-1;//更新答案 } return ans; } int main(){ scanf("%s",a); n=strlen(a); change(); //printf("%s\n",s); printf("%d",manacher()); return 0; }
参考
这篇关于manacher 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升