manacher算法判断回文串的时间复杂度最低,为\(O(n)\).
其他判断回文串的算法,例如:
二分+hash, 后缀数组,他们的时间复杂度都是\(O(nlogn)\)
manacher算法
不断的维护三个属性
- p[i]:以i字母为中心的最长的回文半径
- id:最长回文半径的坐标
- mx最长p[i]做能触及的最右边+1,相当于是一个开区间
具体看代码
题目
题意
题解
AC代码
|
|
manacher算法判断回文串的时间复杂度最低,为\(O(n)\).
其他判断回文串的算法,例如:
二分+hash, 后缀数组,他们的时间复杂度都是\(O(nlogn)\)
不断的维护三个属性
具体看代码
|
|
本文标题:manacher算法
文章作者:Babydragon
发布时间:2018-03-12, 18:19:17
最后更新:2018-03-23, 13:31:04
原始链接:http://baolintian.github.io/2018/03/12/manacher算法/
许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。