Manacher’s Algorithm，中文名叫马拉车算法，是一位名叫Manacher的人在1975年提出的一种算法，解决的问题是求最长回文子串，神奇之处在于将算法的时间复杂度精进到了O(N)。

1 预处理

首先我们解决下奇数和偶数的问题，在每个字符间插入 “#”，并且为了使得扩展的过程中，到边界后自动结束，在两端分别插入 “^” 和 “$”，两个不可能在字符串中出现的字符，这样中心扩展的时候，判断两端字符是否相等的时候，如果到了边界就一定会不相等，从而退出循环。经过处理，字符串的长度永远都是奇数了。

1574136671999.png

首先我们用一个数组 P 保存从原数组index为中心可扩展回文的最大个数，而它刚好也是去掉 “#” 的原字符串的总长度。例如下图中下标是 6 的地方，可以看到 P[ 6 ] 等于 5，所以它是从左边扩展 5 个字符，相应的右边也是扩展 5 个字符，也就是 “#c#b#c#b#c#”。而去掉 # 恢复到原来的字符串，变成 “cbcbc”，它的长度刚好也就是 5。即最大回文半径=原数组最大回文长度。

1574136701374.png

2 求原字符串下标

原字符串下标index = (i - P[i]) / 2

例如，上图我们找到 P[ i ] 的最大值为 5，也就是回文串的最大长度是 5，对应的下标是 6，所以原字符串的开头下标是（6 - 5 ）/ 2 = 0。所以我们只需要返回原字符串的第 0 到 第（5 - 1）位就可以了。

3 求关键数组P[i]

从上面两个步骤可以看出，数组P[i]是整个算法的关键。

我们用 C 表示回文串的中心，用 R 表示回文串的右边边界，所以 R = C + P[ i ]。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串。那么如何求P[i]呢，如下图：
1574136777481.png
用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的对称位置，则P[i] = P [ i_mirror ] = 3。

如下三种情况，不能世界上面上一句的公式，需要用中心扩展法另外处理：

  • P [i_mirror ] 遇到了原字符串的左边界：
  • P [i_mirror ] + i 超过右边界
  • I = R

4 更新C和R

就这样一步一步的求出每个 P [ i ]，当求出的 P [ i ] 的右边界大于当前的 R 时，我们就需要更新 C 和 R 为当前的回文串了。必须保证 i 在 R 里面，所以一旦有更右边的 R 就要更新 R。

1574136844913.png

此时的 P [ i ] 求出来将会是 3，P [ i ] 对应的右边界将是 10 + 3 = 13，所以大于当前的 R，我们需要把 C 更新成 i 的值，也就是 10，R 更新成 13。

5 源代码

  1. //思路2：马拉车算法，线性求最长回文子串
  2. //预处理函数
  3. string preProcess(string s)
  4. {
  5.         int n = s.size();
  6.         if (n == 0)
  7.                 return "^$";
  8.         string retStr = "^";
  9.         for (int i = 0; i < n; i++)
  10.         {
  11.                 retStr += "#";
  12.                 retStr += s[i];
  13.         }
  14.         retStr += "#$";
  15.         return retStr;
  16. }
  17. //马拉车算法
  18. string longestPalindrome(string s)
  19. {
  20.         string T = preProcess(s);
  21.         int n = T.size();
  22.         vector<int> P(n, 0);
  23.         int C = 0, R = 0;
  24.         //找出P的最大值，即最大回文长度，就可以得到原字符串的起始index和最后的回文字符串
  25.         int maxLen = 0;
  26.         int centerIndex = 0;
  27.         for (int i = 1; i < n - 1; i++)
  28.         {
  29.                 int i_mirror = 2 * C - i;
  30.                 if (R > i)
  31.                 {
  32.                         P[i] = min(R - i, P[i_mirror]); // P[i] = P[i_mirror],防止超过R，加min函数
  33.                 }
  34.                 else
  35.                 {
  36.                         P[i] = 0; //等于R，意味着i当前是#字符，所以直接设置0
  37.                 }
  38.                 //处理三种特殊情况，使用中心扩展方法,因为起始和终结字符分别为^和$，所以while循环最终会退出
  39.                 while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
  40.                 {
  41.                         P[i] +=1; //检查超过边界之后是否还有可以回文的字符，有则加1
  42.                 }
  43.                 //判断是否需要更新C和R
  44.                 if (i + P[i] > R)
  45.                 {
  46.                         C = i;
  47.                         R = i + P[i];
  48.                 }
  49.                 //保存最大回文半径和中心点
  50.                 if (P[i] > maxLen)
  51.                 {
  52.                         maxLen = P[i];
  53.                         centerIndex = i;
  54.                 }
  55.         }
  57.         int start = (centerIndex - maxLen) / 2; //获取起始index
  58.         return s.substr(start, maxLen);
  59. }