『浅谈』manacher算法
2022/7/10 14:24:19
本文主要是介绍『浅谈』manacher算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
『浅谈』manacher算法
简介
作为一种求回文子串的算法,manacher几乎总是能在O(n)的时间求出
在有些时候manacher需要
朴素算法
,请先复习朴素算法
即该算法通过下述方式工作:对每个中心位置 ,
在比较一对对应字符后,只要可能,该算法便尝试将答案加1。-----oi_wiki
正文
- 首先为了避免奇偶要单独处理的情况,可以考虑在字符中间加入分割符使字符串长度固定为偶数
- 如abc变成@#a#b#c# (@是为了方便判断越界)
- 变量铺垫
- s表转换后(加入分割符)的字符串
- len[i]表以i为中心点的回文串中,i到右(或左)边界的长度
- l表上一次取得的最大的回文串左边界
- r表上一次取得的最大的回文串右边界
- mid上一次的终点
- j表i相对于mid的对应点(已经求出的)
若存在j,则j=mid-(i-mid)=2*mid-i
- i表一回文串的中点
- mx表最大的长度
- then
for(i 1~s长度 (遍历)) 枚举中点 if(i在以mid为中心的回文串内) if(以i为中点的回文串的右端在以mid为中心的内部) 如图 [l [ j ] mid [ i ] r] 因为 j是i相对于mid的对称点,回文串倒着显然还对称 所以len[i]大于或等于len[j] 先让len[i]=len[j],后面再用朴素算法把大于的求出来 所以 for(len[i]=len[j];s[i-len[i]]==s[i+len[i]];len[i]++); else 如图 [l [ j ] mid [ i r] ] 此时 以i为中点的回文串只确定了(r-i) 所以len[i]大于或等于r-i 所以再用朴素算法求剩下的 for(len[i]=r-i;s[i-len[i]]==s[i+len[i]];len[i]++); else 此时说明以i为中点的回文串没有一点是确定的 所以len[i]大于或等于1(一个字符也是回文串) 直接朴素算法 for(len[i]=1;s[i-len[i]]==s[i+len[i]];len[i]++); if(以i为中点的回文串的右边界大于上一次的r) 更新r,mid mx=max(mx,len[i]); 最后答案=(mx-1)/2*2=mx-1 -1删除末尾的'#' /2把#删掉 *2是把回文串的另一半加上
CODE(cpp)
int mnc(string s) { int len[s.size() << 1], mid, r = 0,mx = -1; for (int i = 0; i < (int)s.size(); i++) { if(i<r)//i在以mid为中心的回文串内 { int j = mid - i + mid; if (len[j]<=r-i)//以i为中点的回文串的右端在以mid为中心的内部 for(len[i]=len[j];s[i-len[i]]==s[i+len[i]];len[i]++); else for(len[i]=r-i;s[i-len[i]]==s[i+len[i]];len[i]++); } else for(len[i]=1;s[i-len[i]]==s[i+len[i]];len[i]++); if(len[i]+i>r)//更新 { r=len[i]+i; mid=i; mx=max(mx,len[i]); } } return mx - 1; }
这篇关于『浅谈』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功能效果提升