Manacher算法

简介

Manacher 算法是一个 O(n) 时间复杂度求解字符串的最长回文子串的算法，其思想类似 KMP 算法，核心思想在于利用回文的对称性，用空间换时间，将已经计算过的最长子串长度存储起来，降低后续的计算量。其遍历字符串中每个字符，计算以其为中心的最长回文子串，同时利用之前的信息减少计算。

核心思想

以下为个人总结的几个重点

字符串预处理

为了同时处理偶数长度和奇数长度的字符串，采用一个 trick 来将字符串统一为奇数长度，即在字符之间和首尾添加一个原字符串不存在的字符，下文以 # 为例；为了进一步减少界判断的麻烦，可以在前面的基础上，再额外在首尾添加两个不存在的字符，用于标识边界。

经过以上操作后，长度为 n 的字符串一定可以添加 n+1 个 # 和两个首尾标识，总长度变为 2n+3，一定为奇数。

以下是一个示例：

长度数组的推导

使用一个数组 T[] 来记录以 i 为中心的最大回文子串半径（不包括中心），即以 i 为中心的最大回文子串索引为 [i-T[i], i+T[i]]。

下面为了方便说明，使用未扩充的字符串来说明，长度为奇数。

可以发现，以红色的 a 为中心的回文子串，其左边和右边的 T[] 是以索引 2 为中心对称的，这样在计算 3,4 的最长子串时，就可以直接使用 T[0], T[1] 这些之前计算好的值，即 T[3]=T[1], T[4]=T[0] 以达到减少计算的目的。

但是镜像一定是对的吗？显然不！

假设以上选取的字符串 ababa 是其他字符串的一部分，考虑以下几种情况：

右边还有字符串

右边黄色部分是额外的字符串，可以发现在这种情况下，T[3]>T[1], T[4]>T[0]

左边还有字符串

左边黄色部分是额外的字符串，简单分析可以发现在这种情况下，T[1]>T[3], T[0]>T[4]

那么结合以上两种情况，什么时候对称是对的，什么时候不对？不对时要怎么获得正确的值？

考虑下面这个字符串，以 b 为中心的最长回文子串范围为 [0,6]，索引 7 超出了范围，使用黄色标注。

绿色部分为关于 b 对称相等的，红色部分为不相等的。

可以发现，当 i 的最长回文子串是中心的最长回文子串的子集时，对称成立。以 s[5] 为例，s[5] 的最长回文子串为 aaa，此时子串的索引范围是 [4,6]，以 b 为中心的最长回文子串索引范围是 [0,6]，显然 [4,6] 是 [0,6] 的子集。那么不成立的情况呢？以 6 为例 6+1=7 > 6，所以此时超出范围，对称可能不成立，即实际值会大于等于对称的值。

由于算法是从左往右推导，下面考虑左边有字符串的情况：

同理，以 s[0] 为中心的最大回文子串超出了以 b 为中心的最大回文子串范围，所以 T[6] < T[0]。

那么我们知道了问题所在，要如何解决这个问题？依旧以上图为例，假设我们此时要计算 T[6]，我们要如何利用已有的数据来简化计算？

很简单，那就是利用对称位置上的值，以 b 为中心，6 的对称位置为 T[2*3 - 6] = T[0]，但是根据上文 T[0] 是偏大的，所以我们不能直接拿来用，而是只取其属于 b 的最长回文子串范围内的部分。

索引为 i 的最长回文子串左边界可以通过 i - T[i] 计算得到，下面取索引为 0 的最长回文子串左边界为 a_left_border = 0 - T[0] = -2，b 的最长回文子串左边界为 b_left_border = 3 - T[3] = 0，在已知 a 的最长回文子串左越界的情况下，a_left_border < b_left_border，s[0] 到 b 的左边界距离为 dis = idx_a - b_left_border = 0 - 0 = 0，也就是我们实际能取的距离是 dis = 0，为了进一步简化 dis 的计算，我们可以利用以 b 为中心的对称性，dis 等于 s[6] 的对称点 s[0] 到 b_left_border 的距离，那么就也等于 s[6] 到 b_right_border 的距离，即 dis = 6 - (3 + 3) = 0。
用公式来表达就是

i = 6;
center = 3;
mirror_i = 2*center - i = 0;
left_border = center - T[center] = 0;
right_border = center + T[center] = 6;

dis = right_border - i = 0; // dis = mirror_i - left_border;
T[i] = min(dis, T[mirror]);

T[i]中心扩展

综上，我们找到了当对称点最大回文子串出现越界时的处理方法，当然，并不是 T[i] = min(dis, T[mirror]) 这个值就是 T[i] 的最终结果，因为右边还有未考虑的字符，也就是 T[i] 还有可能变大，此时就使用中心扩展算法，该算法不是本文的重点，此处不多赘述。

伪代码如下

while(s[i-T[i]-1] == s[i+T[i]+1]){
  T[i]++;
}

中心的移动

通过上文可以发现，判断 i 是否越界重点是中心最长子串的左右边界，代码中常取最右边界，当新计算出的 i+T[i] 大于之前中心的最右边界时，我们可以更新中心到 i。若 i>=right_border 则直接进行中心扩展。

MISC

综上，我们可以把任意字符串输入转换为奇数长度的字符串，又有了对于奇数长度字符串，利用 T[i] 降低时间复杂度的方法，只需把两者结合即可。

以下图为例：

那么对于扩增后，长度为 2n+3 的字符串，我们可以求得其最长回文子串的半径，我们要如何获得原串的最长回文子串的长度？

根据上图可以发现，两者是相等的。

证明非常容易，对于扩增后的字符串，设 T[i] = n，则总长度为 2n+1，而对于原串中长度为 n 的子串，其扩增后长度也是 2n+1，故 T[i] 即是扩增后最长子串半径，也是原串最长长度。

原字符串的索引到扩增后索引的映射关系为 i -> 2i+2，对于扩增后字符串起始点为 center-T[center]，映射到原字符串索引则为 (center-T[center])/2。

证明：
容易证明，最长子串的左右边界点所在的字符一定是 #（不考虑首尾标记符），否则一定存在至少一个更大的子串，其在原有子串的基础上向左右扩展一个字符。
对于原串的任意字符 c，其在原串的索引为 i，则在扩展串中的索引一定为 2i+2；在原串中以 c 为左边界的最长回文子串，在扩展后左边界索引一定是 2i+1，即字符 c 左边的 # 符号，由于代码取整的特点 (center-T[center])/2=(2i+1)/2=i。
证毕.

代码

以下是一份参考代码 (Java)

Leetcode: 5. Longest Palindromic Substring

public String longestPalindrome(String _s) {
    StringBuilder sb = new StringBuilder();
    sb.append('^');
    sb.append('#');
    for (char c : _s.toCharArray()) {
      sb.append(c);
      sb.append('#');
    }
    sb.append('@');
    String s = sb.toString();

    // record the maximum radius and center index
    int maxRadius = 0, maxCen = 0;

    int[] T = new int[s.length()];
    int center = 0;
    for (int i = 2; i < s.length() - 1; i++) {
      if (i < center + T[center]) {
        int mirror_i = 2 * center - i;
        int dis = center + T[center] - i;
        T[i] = Math.min(T[mirror_i], dis);
      }
      // expand around center i
      while (i - T[i] - 1 >= 0 && i + T[i] + 1 < s.length() &&
          s.charAt(i + T[i] + 1) == s.charAt(i - T[i] - 1)) {
        T[i]++;
      }
      // update center index
      if (i + T[i] > center + T[center]) {
        center = i;
      }

      // record the maximum radius
      if (T[i] > maxRadius) {
        maxCen = i;
        maxRadius = T[i];
      }

    }
    int begin = (maxCen - T[maxCen]) / 2;
    return _s.substring(begin, begin + T[maxCen]);
}