# Manacher's algorithm

Manacher’s algorithm 以$O(n)$的线性时间求一个字符串的最大回文子串。

### 1. 预处理

S = a b a a b a
T = # a # b # a # a # b # a #

S = a b a a b a
T =    # a # b # a # a # b # a #
T = $# a # b # a # a # b # a # 这样，预处理工作完成，下面进入manacher算法的核心部分。 ### 2. manacher’s algorithm 这里，定义一个数组$p[]$和 两个变量$r$和$c$。$p[i]$表示以位置$i$为中点的最大回文子串的长度。$r$表示当前所有检测过的位置所能到达的最右端。$c$为与$r$对应的$i$的位置，与$r$同时更新，实际上$c+p[i]=r$。 回忆下一个$O(n^2)$的做法： 从左到右对字符串进行扫描，以每个位置为中点，向两边扩张，并记录最大长度和相应的位置（对于偶数，类似的再处理一遍即可）。 这种算法的空间复杂度为$O(1)$，是很优秀的，但是，对于每一个位置，都从长度为0开始向两边扩展，这是导致时间复杂度高的一个最主要的原因。 而manacher算法则是额外使用一个$p[]$数组记录最大回文子串的长度， 因存在对称关系，数组$p[]$的值能够被充分利用，部分$p[i]$的值可以在$O(1)$的时间确定。 从而使得算法的复杂度降为$O(n)$。 这种思路类似于KMP算法，充分利用前面已经匹配过的有用信息。 如何计算数组$p[]$的值呢？ 我们分两种情况：${i}’$代表$i$关于中心$c$的对称点，计算公式为${i}’=2 \times c - i$至于为什么是两种情况，请看下面的参考文献，这里图我就不摆了。 这样我们可以轻松得到P数组的值 T =$ # a # b # a # a # b # a #
P = 0 0 1 0 3 0 1 6 1 0 3 0 1 0

### 4. 算法复杂度

$\text{manacher}$算法只需要线性扫描一遍预处理后的字符串。

1. $\text{ if } (i < r ) \;\;O(1)$ 时间可以确定
2. $\text{ otherwise } O(n)$匹配，但是在情况2下，每次扫描都是从$r+1$开始的，且$r$自身的变化情况是单调递增的，这样可以保证，字符串T中的每个字符最多被访问2次，所以，该算法的时间复杂度是线性$O(n)$，事实上，$\text{while}$循环执行的总次数是线性次的。