我最近阅读了一篇关于 Manacher 算法的维基百科文章，在看到示例实现和数十个其他实现之后……说实话，我不知道这个算法是如何线性的。在我看来，最好的情况是 O(n+n/2)，但这不是线性的，不是吗？
http://en.wikipedia.org/wiki/Longest_palindromic_substring
对于原始字符串中的每个字符，我们尝试在两个方向上扩展 P 数组，直到到达字符串边界或不满足对称属性。如果只是这样，这意味着 O(n^2)，但如果有额外的观察，结果会小于这个值。我最多仍然可以把头降低到 O(n+n/2)，但不能降低到 O(n)，因为这本质上意味着内部嵌套循环 o(1)。任何高于此值的值都会破坏整个算法的线性度。
简而言之，这个算法是如何线性的？
O(n + n/2) 是线性的，O(n+n/2) ~ O(n)
时间仍然与n成正比。
或者，更精确地说，当 n 趋向无穷大（以及当它不是无穷大时）的 (n+n/2) / n 的极限是一个有限常数。所以 O(n+n/2) 和 O(n) 是等价的。
该算法的复杂度不是 O(N)，而是 O(M)，其中 M 是所有回文子串的数量 你可以看到一些字符串，复杂度是 N^2 因为有 N^2 回文 示例：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (N a)