和manacher有关的乱写
2024-09-01 06:04:18
当初学kmp hash的时候被教导manacher非常的鸡肋
今天因为一篇神奇的题解我忍不住颓废了两节课把它学了
思路，代码都比较好懂
虽然它不如各种自动机霸气，唯一的功能貌似就是$O(n)$求出所有回文串..
不过它的时空花费都比较小（滑稽）
首先为了解决回文串的奇偶问题，在每两个字符中间和整个串的两边都加上一个特殊字符（只要不在原串出现就可以）
然后发现所有的回文串都是奇串，只需要求出以每个点为对称中心的回文串即可
定义一个数组$p[i]$,表示以$i$点为对称中心的回文串的长度+1再/2（其实就是i从这个点到边界的长度）
维护一个变量$center$，表示之前处理过的回文串中，最右端点最靠右的中心
由回文串的性质，我们发现如果这个点关于$center$的对称点的最长回文串被$center$的串完全包含
那么这个$p$就和之前的相等，直接$O(1)$
否则向右暴扫更新右端点，是单调的，所以总的复杂度$O(n)$
最新文章
- 缓存淘汰算法--LRU算法
- ABAP程序互调用：SUBMIT、CALL TRANSACTION、LEAVE TO TRANSACTION
- hdu 4966 GGS-DDU (最小树形图）
- 黑客语（Leet）
- arcgis server 10.2安装后，忘记Manager的用户名和密码
- 最近一段时间开发客户端app的感悟
- 【JavaScript】关于prototype
- Android 联系人字母排序（仿微信）
- MyEclipse导入ant项目——Java编程思想
- 我的Python成长之路---第三天---Python基础（9）---2016年1月16日（雾霾）
- 201521123059 《Java程序设计》第七周学习总结
- vue-cli webpack3扩展多模块打包
- 006-Python函数
- linux后台执行./run.py提示python syntax error near unexpected token `('
- LATCH_EX
- Non-technical Blog Recording on Day of Sep. 19th 2017 in Retrospection.
- 编程，计算data段中的第一组数据的3次方，结果保存在后面一组dword单元中
- easyui datagrid 动态改变行背景色
- Spark2 Dataset分析函数--排名函数row_number,rank,dense_rank,percent_rank
- MySQL 字符串拼接