回文字符串 Manacher
2024-10-19 17:25:21
1. Manacher
忘光了,忘光了。
首先将字符串所有字符之间(包括头尾)插入相同分隔符,再在最前方插入另一个分隔符防止越界。
设以 \(s_i\) 为对称中心的回文串中,最长的回文半径为 \(p_i\)。记录在所有遍历过的位置中(\(1\sim i-1\)),以任意一个点为对称中心的回文串的右端点最大值 \(r\),即 \(r=\max_{j=1}^{i-1}s_j+p_j-1\),记 \(d\) 即为取到这个最大值的对称中心。注意 \(r\) 和 \(d\) 是实时更新的。
对于当前位置 \(i\):
若 \(i>r\),则暴力求 \(p_i\),此时每次扩展都会将 \(r\) 向右移动 \(1\);
若 \(i\leq r\),则先将 \(p_i\) 赋值为 \(\min(r-i+1,p_{2d-i})\),再逐位扩展。
说明:因为位置 \(2d-i\) 与 \(i\) 是对称的(在 \(d\) 的最长回文半径范围内),所以在 \([d-p_d+1,d+p_d-1\ (r)]\) 范围内,\(2d-i\) 的回文串也是 \(i\) 的回文串。若 \(p_{2d-i}<r-i+1\),那么根据对称性,\(p_i\) 的最终值就等于 \(p_{2d-i}\)。否则 \(p_i=r-i+1\),每次扩展都会将 \(r\) 向右移动 \(1\)。
综上,总时间复杂度为 \(\mathcal{O}(n)\)。
最新文章
- css 选择器优先级
- Spring(3)
- html基础 2
- ISO 14229 简介 转载
- sql截断日志
- spring+redis实现缓存
- Fedora 14配置vsftp服务步骤
- sort()的多种用法
- 数据可视化开源系统(python开发)
- Qt之日志输出窗口
- 不同版本(2.3,2.4,2.5) web.xml 的web-app头信息
- HDU 1671 Phone List (Trie)
- swiper 逆向轮播
- Init wms goodlocation data
- Mac 下eclipse安装Lombok插件
- echo 在shell及脚本中显示色彩及闪烁警告效果
- ntpd、ntpdate、hwclock的区别
- yum all installed dependent packages while removing a package in centos 7?
- 20155318 《网络攻防》 Exp8 Web基础
- IPC通信:Posix消息队列
热门文章
- the Agiles Scrum Meeting 3
- Python爬取COVID-19疫情监控实战
- 华为HCIP-Eth-trunk原理知识点
- Dubbo框架协议总结
- 四种 AI 技术方案,教你拥有自己的 Avatar 形象
- 目录扫描工具 dirsearch 使用详解
- 第一课 Dubbo背景及原理
- 在同级路径下,SpringBoot两种类型的配置文件(.properties/.yml)同时存在时,配置优先级如何处理?
- Part 17 Consuming ASP NET Web Service in AngularJS using $http
- Swift学习笔记(一)