这个方法是从中心扩展法演化来的，中心扩展的时间复杂度是O(n^2)，以每个字符为中心，需要遍历一次，然后查找回文需要再嵌套一层，所以复杂度是O(2n*(n-1)) = O(n^2)。
具体的算法可以参考下面这个 Manacher算法的详细讲解
但是一直没搞明白为啥Manacher的复杂度是O(n)，觉得他还是要做两次遍历。今天深究了一下，简单理解，主要看他那个右边界R，每次更新的时候，R都会往右走或者不变，不会回退。所以所有的过程就是R从最左走到最右的过程，复杂度是O(n)。按照上述参考文章中说的情况，第二种的1，2是不需要计算的，复杂度O(1)，而剩下来的两种需要去找回文，这两种都会更新R。
当然也可能有人会想，万一很多字符都需要找回文呢，回文又比较长呢，那不还是O(n^2)。之前我纠结的也是这个，后来想起小学的奥数题，两辆车，后车追前车，有辆摩托车在他们之间来回跑，问辆车相遇的时候摩托走了多少路。这个题不需要去算每次的路程相加，只要相遇时间乘以速度就行了。就像不要去纠结几个字符，每个字符的回文长度，只要看R就好了。
不知道几年之后自己看这个还能看懂么。。
求最长回文字串，用了一个Manacher 算法。 以下是根据题目要求用JavaScript完成的代码：
在 leetcode 刷题刷到求字符串的最长回文字串，而马拉车算法(Manacher's Algorithm), ...
这个方法是从中心扩展法演化来的，中心扩展的时间复杂度是O(n^2)，以每个字符为中心，需要遍历一次，然后查找回文需...
最长回文子串 public class Manacher { public static int min(int ...
问题描述 给一个字符串，求其最长回文字串 样例 Input："babad"，Output："bab"，Note："...
最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串，求它的最长回文子串长度...
Manacher's Algorithm俗称马拉车算法，对于求字符串中最长回文子串效率极高。 在求最长回文子串的时...
1 竖式问题 2. 最长回文字串
目录结构如下： 引入 Manacher算法详解 例题 References 1. 问题引入 最长回文子串（Long...
Manacher 解决最长回文子串问题 引入两个辅助变量 id, mx先预处理插入#，再分两种情况： 回文串 p[...
本文标题：Manacher最长回文字串
本文链接：https://www.haomeiwen.com/subject/vvzyjqtx.html
网友评论