Manacher算法

Manacher算法

Manacher算法的经典应用场景是：从一个给定字符串中，高效地找出其最长的回文子串。但是其用法不仅仅是这一种场景。

求一个字符串的最长回文子串的传统做法就是遍历每个字符，把它当成对称轴，向左右两边扩充去算回文直径。但是这个方法碰上给的字符串是偶数长度时，就会漏掉一些偶数长度的回文子串。eg：

12 2131221 以黑色的2为对称轴向左右扩时，并不能找到第一个1221 这个偶数长度的回文子串。

所以有了Manacher算法，不仅找得全，而且时间复杂度达到最优的O(n)

前置概念

算法中引入了几个新的概念，这里来一一解释。

1. 将一个给定的字符串处理成特定的字符串 eg：aa3werew ----> a#a#3#w#e#r#e#w#，给定字符串的长度为$n$，则填充的字符个数为$n+1$ ，所以无论给定的字符串是偶数长度还是奇数长度，最后处理过后都是奇数长度。并且找出的任意一个回文子串长度都是奇数。
2. 1. 回文直径 eg：w#e#r#e#w 的回文直径为9；2. 回文半径 以中心点到边界的距离+1，eg：w#e#r#e#w 的回文半径为5。
3. 最右回文边界R 就是遍历到当前字符时，之前所有字符找到的最大回文边界。R初始为==-1== eg： a#a#3#w#e#r#e#w# 到a时，只能以自己作为回文子串，那么a的回文直径是从[0, 0]，并且大于R，那么R更新为0；到#时，向左右找到的最大回文直径为[0, 2]，2大于R，再次更新R为2.
4. 最右回文边界的中心点C 就是每次更新R时，记录那个使R更新的字符的位置。上一条讲的那样，R更新为2时是因为#这个字符，该字符的位置为1，所以C为1.C初始也为==-1==。所以R，C同步更新。
5. 准备一个和扩充后的字符串长度相等的数组，里面对应记录每个字符的回文半径。

手动算法流程

1. 给定一个字符串，将其扩充为标准处理字符串。将R，C初始化为-1

2. 遍历每个字符。当来到一个新字符时，会有两种分类情况：

   1. 当前字符的索引 > R 这种情况没有优化，此时只能对该字符左右同时扩充寻找以该字符为中心的最长回文子串，找到后根据情况决定是否更新R和C

   2. 当前字符的索引 < R （先不考虑刚好等于R的情况），那么此时一定有如下的关系图成立：

      ​ L j C i R ,
      i 为当前字符位置，j 是i关于C 的对称点，L是R关于C的对称点，也就是说[L, R]整个就是 一个回文子串。在这种情况下，又会有3种细分情况

​ 1. j的回文区域完全在 [L, R] 内部 -----> L ( j ) i R ， 如果是这种情况那么i 的回文 长度不用扩张，直接可以判定等于j 的回文长度。证明如下：

​

​ 2. j的回文区域超出 [L, R]，但不是刚好压在L，R上 举例：

			![](https://img-blog.csdnimg.cn/c064591e73684b76ba666e8d486ef62b.png)
1

​

​ 3. j的回文区域左边界刚好等于L ，此时同样可以确定i的回文区域至少是第2种情况中的[R’, R]，但 是不能确定还能不能往外扩，只能确定至少是[R’, R]，所以这种情况下，也是需要向左右扩充的。

代码实现

public static char[] process(String s){
   char[] res = new char[2 * s.length() + 1];
   char[] ori = s.toCharArray();
   int index = 0;
   for (int i = 0; i < res.length; i++) {
      res[i] = (i & 1) == 1 ? ori[index++] : '#';
   }
   return res;
}

public static int manacher(String s){
   if (s == null || s.length() == 0)
      return 0;
   char[] ori = process(s);
   int[] res = new int[ori.length];    // 回文半径数组
   int R = -1, C = -1;             // 这里的R指的是回文最右边界的再往右一个位置， 中心点C
   int max = Integer.MIN_VALUE;
   for (int i = 0; i < ori.length; i++) {
      // 先确定当前元素至少的回文区域。如果R > i，不管落入4种情况的哪一种，都是 Math.min(res[2 * C 			 - i], R - i)
      res[i] = R > i ? Math.min(res[2 * C - i], R - i) : 1;

      // 4种情况中，只有两种需要左右扩充，但是如果将扩充算法写到对应的情况下会代码冗余，所以写成如下这				样，4中情况都会进入该
      // 扩充算法，但是原有的不需要扩充的两种情况进入该循环后会直接失败，所以效果等价。
      while (i + res[i] < ori.length && i - res[i] > -1){
         if (ori[i + res[i]] == ori[i - res[i]])
            res[i]++;
         else
            break;
      }
      // 判断是否需要更新R，C
      if (i + res[i] > R){
         R = i + res[i];
         C = i;
      }
      // 记录当前最大值
      max = Math.max(max, res[i]);
   }
   // 经发现：标准流字符串中的回文半径-1，就可以得到原始字符串中的回文直径
   return max - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

思考

将字符串扩充为标准处理串时添加的符号一定要是原字符串中没出现的吗？