manacher浅析
2024-10-14 22:27:11
manacher算法的输入是一个字符串,可以计算出以每个字符为中心的最长回文子串的半径。为了避免讨论奇数偶数,将原串的每两个字母之间以及前后各加一个特殊字母,比如'#',那么对于abcbb就变成了 #a#b#c#b#b#,串的长度变成了11,我们用dp[i]表示以i为中心的最长回文的半径,那么上面的串的dp值如下:
# a # b # c # b # b #
1 2 1 2 1 4 1 2 3 2 1
设串为S,那么S[i-dp[i]+1,i-1]=S[i+1,i+dp[i]-1]。
我们从前向后依次计算每个位置的dp值。设现在计算到了i位置,之前所有位置j的最大的j+dp[j]的位置为id,Max=id+dp[id]。
下面分三种情况(设j=2*id-i,即j为i关于id的对称点):
(1)Max-i>dp[j]:如下图,这说明以j为中心的回文串完全在以id为中心的回文串的内部,那么由于对称性可得,以i为中心的回文串的半径dp[i]=dp[j]。
(2)Max-i<=dp[j]:如下图,那么以j为中心的回文串超出了以id为中心的回文串,那么绿色方框内的部分必然是对称的,那么dp[i]至少等于Max-i。外面的不能确定,我们可以强行匹配。
(3)Max<=i,我们强行匹配这种情况即可。
代码如下,为了方便,在最开始加入一个特殊字母'$'
void manacher(char *s,int n,char *S,int dp[])
{
int cur=;
S[cur++]='$';
S[cur++]='#';
for(int i=;i<n;i++) S[cur++]=s[i],S[cur++]='#';
n=cur;
int Max=,id=;
for(int i=;i<n;i++)
{
dp[i]=Max>i?min(dp[*id-i],Max-i):;
while(S[i+dp[i]]==S[i-dp[i]]) dp[i]++;
if(i+dp[i]>Max) Max=i+dp[i],id=i;
}
}
最新文章
- 构造函数this和base的区别
- Git基本常用命令
- ACM/ICPC 之 最短路径-dijkstra范例(ZOJ2750-POJ1135(ZOJ1298))
- LeetCode Count of Smaller Numbers After Self
- dir:一行代码,提取出所有视频文件名称及路径
- geotools导入shp文件到Oracle数据库时表名带下划线的问题解决
- 操作数组的工具类Arrays
- mysql 创建用户与授权、修改密码
- JPA 系列教程11-复合主键-2个@Id
- (简单) HDU 5154 Harry and Magical Computer,图论。
- 关系型数据库MySql-模糊搜索优化(like %abc%):全文搜索引擎技术选型
- C#基础知识-基本的流程控制语句(三)
- Java中File
- oracle多表连接查询竟然还有这种操作
- Android为TV端助力:EventBus跨进程发送消息
- Cookiecutter: 更好的项目模板工具:(3)高级用法
- 工作流调度器azkaban
- Kubelet bootstrap认证配置步骤
- java设计模式-菜鸟网络
- 即时通信(IM)和实时通信(RTC)的区别
热门文章
- original.txt和提交的页面输出的文字的混合文件
- tomcat重启session不过期的处理
- EmguCV 如何从数组中创建出IntPtr
- 【iCore3 双核心板】例程三:EXTI中断输入实验——读取ARM按键状态
- [troubleshoot][daily][archlinux][pacman] pacman 与 pip 包文件冲突
- 深入理解Spark RDD
- 弹出框以及提示插件lghdialog.js的使用
- (地址)propedit安装说明的地址
- oracle数据导出工具sqluldr2
- ReentrantLock的实现语义与使用场景