一、算法背景
Manacher算法，中文名马拉车算法，用以解决求字符串中的最长回文子串。传统的寻找最长回文子串的方法是从左到右遍历字符串的每个字符，同时以每个字符为回文中心向左右两侧扩散寻找，当字符串中存在大量回文子串，比如在极端情况下 $“aa…aa”$ ，算法的时间复杂度是 $O(N^2)$ 。而Manacher算法能够把寻找最长回文子串的时间复杂度降到 $O(N)$ 。
二、字符串预处理
假设要处理的字符串是 $“abbabb”$ ，由于回文串有奇回文和偶回文，比如 $“bab”$ 是奇回文， $“abba”$ 是偶回文，奇回文的对称轴是一个字符，偶回文的对称轴是两个字符，为了消除这种差异，首先要对字符串预处理，在每个字符的两侧都添加占位符，比如 $“\sharp”$ ，原来的字符串就变成了 $“\sharp a\sharp b\sharp b\sharp a\sharp b\sharp b\sharp ”$ 。对于其中的每个回文串，预处理相当于在每个字符的右侧添加占位符，变成偶回文，再在整体回文串的左侧添加一个占位符，变成奇回文。比如上述两个回文串变成了 $“\sharp b\sharp a\sharp b\sharp ”$ 和 $“\sharp a\sharp b\sharp b\sharp a\sharp ”$ ，长度分别是7和9，都是奇回文。
二、计算最长回文子串半径
除了对字符串的预处理，算法还需要一个辅助数组 $p$ ，设预处理后的字符串是 $arr$ ，则 $p[i]$ 表示以 $arr[i]$ 为回文中心的最大回文半径。由于所有回文串都是奇回文，所以回文半径可以表示为 $(回文串长度+1)\div 2$ ，也就是包含回文中心的回文串的一半。比如下表中， $p[3]=2$ 表示以 $arr[3]$ 为回文中心的最长回文子串是 $“\sharp b\sharp ”$ ，回文半径是2，即 $“\sharp b”$ 的长度。
| i ： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| arr： | # | a | # | b | # | b | # | a | # | b | # | b | # |
| p ： | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 6 | 1 | 2 | 3 | 2 | 1 |
计算数组 $p$ 需要两个辅助变量， $maxright$ 表示遍历至此发现的回文串所能达到的最右边界， $center$ 表示到达最右边界的回文串的回文中心。当遍历到 $arr[i]$ 时，要计算的是以 $arr[i]$ 为回文中心的最大回文半径，由于 $center$ 和 $maxright$ 是当前已知的回文中心和回文边界，所以一定是在之前的步骤算出来的，所以必有 $center<i<maxright$ ，又因为 $arr[center..maxright]$ 是一个回文串的右半部分，所以在 $arr[0..center]$ 中必有 $i$ 的对称点，记为 $i’$ ，以及 $maxright$ 的对称点 $maxright’$ ，至此，可以确定以下数组下标的位置关系：
Manacher算法的核心就是利用之前步骤算出的 $p$ 数组的值来减少对字符串的遍历。在当前的步骤中就体现在根据 $p[i’]$ 值的情况优化计算 $p[i]$ 的过程，把以 $arr[i]$ 为回文中心的回文串的右边界记为 $iright$ ，关于 $center$ 的对称点记为 $iright’$ ，分为两种情况：
情况一：$p[i’]<maxright-i$
$p[i’]$ 是 $i’$ 到 $iright’$ 的距离，$maxright-i$ 是 $i’$ 到 $maxright’$ 的距离，位置关系如下，
说明以 $arr[i]$ 为回文中心的回文串被完全包含在以 $arr[center]$ 为回文中心的回文串中。必有 $p[i]=p[i’]$
情况二：$p[i’]\geq maxright-i$
位置关系如下，
说明以 $arr[i]$ 为回文中心的最大回文半径至少是 $maxright-i$ ，而 $maxright’$ 左侧与 $maxright$ 右侧的字符是否匹配还不知道，因为 $maxright$ 就是当前遍历到的最右边界，再右边的字符还没遍历到，所以此时可以把 $maxright’$ 和 $maxright$ 当做左右边界向外扩散匹配，而回文中心 $i$ 到 $maxright$ 之间的字符就不必判断了，因为 $p[i’]$ 保证了这一段一定是能匹配成功的。
一句话总结， $p$ 数组的计算过程就是利用算过的 $p$ 数组的值优化左右扩散匹配。
三、最长回文子串起始坐标
算好了数组 $p$ ，其中最大的值就是最长回文子串的半径，但这里得到的长度和坐标都是基于预处理后的字符串 $arr$ ，获取最长回文子串需要知道他在原字符串 $str$ 里的起始点和半径。
| i ： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| arr： | # | a | # | b | # | b | # | a | # | b | # | b | # |
| p ： | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 6 | 1 | 2 | 3 | 2 | 1 |
| str： | a | b | b | a | b | b |
在上图的例子中，基于 $arr$ 得到的回文中心是 $arr[7]$ ，回文半径是 $p[7]=6$ ，而在目标字符串中需要找到的回文串是 $str[1..5]$ 。
回文串在原字符串中的起始坐标是 $index=(i-p[i])\div 2$ ，其中 $i-p[i]$ 是 $arr$ 起点到回文串左边界的距离，在例子中就是 $“\sharp a”$ 这一段，由于最大回文字符串的首尾一定是占位符，所以从 $arr$ 起点到回文左边界这一段中的每个字符只有左侧有占位符，也就是说字符和占位符的数量是相同的，所以式子最后要除以2，才能得到其中所有有效字符的数量，这个去除了占位符的长度就是原字符串 $str$ 中起点到回文左边界的距离。
$str$ 中的回文半径也容易计算。如果 $arr$ 中的回文中心是有效字符，说明这个回文串预处理前是奇回文，回文串的左半部分中每个字符的左侧都有一个占位符，在例子里也就是 $“\sharp b\sharp b\sharp a”$ ，这时真实的回文半径就是 $p[i]\div 2$ 。如果 $arr$ 中的回文中心是占位符，说明这个回文串预处理前是偶回文，回文串的左半部分中每个字符的左侧都有一个占位符，同时多了回文中心上的一个占位符，这时真实的回文半径就是 $(p[i]-1)\div 2$ 。
Manacher算法的 $O(N)$ 时间复杂度可以理解成 $maxright$ 从 $arr$ 起点移动到终点的过程， $maxright$ 左侧的字符都是不必重复匹配的，右侧随着匹配过程不断更新 $maxright$ 的位置。
