Manacher算法的详细讲解

Manacher算法

Manacher算法：在一个字符串中找到最长回文串。

回文：正着念和反着念一样的东西。“121”,“1221”.

第一种方法: 暴力解，时间复杂度O(n*n)。分为两种情况:

思路

从一个位置 i 开始向两边扩，i 位置肯定自己就可以构成回文，继续看 i-1 位置和 i+1 位置是否相等，若相等，则以 i 为中心的字符就扩出来了3个，继续看 i-2 与 i+2 位置…，即：以一个字符为中心向两边扩，奇数长度可以，但偶回文怎么办？举例子： 1221,都无法扩

解决：向整个字符串的两头及中间加一个特征字符，让无论是奇长度还是偶长度的字符串都可以变成奇长度，最后原始字符串最长回文子串的长度为 最大值/2；

该字符串最长回文子串的长度=11/2=5.

注：中间加的特殊字符可任意加，因为 虚轴永远之和虚轴比，虚轴不可能和实轴比。

第二种方法: Manacher，时间复杂度O(n)。

讲述Manacher算法之前，我们要先建立几个概念：

• 回文直径：以一个位置为中心向两边扩，扩出来的整个串的长度。

• 回文半径：一个串开始扩，扩一半的长度。

  这里，我们需要一个辅助数组–回文半径数组：该数组记录从左往右依次开始以每个位置为中心的情况下能够扩出来的回文半径的长度，我们看计算后边的回文半径过程能不能利用前边计算好的回文半径的结论进行加速。

• 最右回文右边界：所有回文半径中最靠右的位置(用R表示)。

举个例子说明吧：

一开始，最右回文右边界R 是在 -1 位置，无效值。当从 0 位置扩时，只能扩到它自己，因此 R=0；扩 1 时，1 没在回文右边界里，发现从 1 扩时可以扩到 2 位置，因此 R=2，当扩 2 位置上的 ‘#’ 时，只能扩到它自己，因此 R=2， 当扩 3 位置的 ‘2’ 时，R=6，即对比字符串，来到的最右位置就就叫做所有回文半径中的回文右边界，扩 4,5 位置时，R 都没有再扩出去，如果没有扩出去，那回文右边界就一直停在 6，直到来到 6 位时，停。

• 回文右边界中心：当到达一个回文右边界时，它对应的中心位置(用C表示)。

  

它俩永远是相伴随的，即： 只要 回文右边界R 没更新，就记录下最早到达回文右边界的位置时，其中心C 在哪。

由于可能有多个都能到达同样的R，例如 “1213121”，当到达 3位置 时，R=6，到 4位置 时，R=6，则我们的 C 就记录的是 R 第一次到达6位置时的中心点位置，如果 R 更往又了，则 C 应该改变。

我们的Manacher就是建立在这几个概念上玩出来的~~

现在开始讲Manacher

Manacher算法其实和暴力解法是非常像的，只是在扩的过程中有加速而已。

为理解起来较为直观容易，我们将出现的情况分为四大类：

第一种可能性: i 不在回文右边界里

假设当前来到的是 i 位置，我们以 i 作为中心向两边扩，看能扩多长。

eg：

扩 0 位置时， R=-1，这就叫 i 不在回文右边界里。

注：二三四中可能性都是建立在一种可能性上的，即： i 位置在回文右边界里

根据 i 做关于 C 的对称点 i’，i’ 的回文半径的具体情况拆分了3种可能性

数组中每个位置为回文半径长度，记录 i’ 的回文区域。

接下来我们依次分析这三种情况：

第二种可能性: i’ 的回文区域整体都在 (L 与 R) 内

i 位置的回文区域不用扩，直接知道答案：和 i’ 一样（证明可用反证法）

第三种可能性: i’ 的回文子串的左区域在 L 外

此时， i 的回文半径就是 i到R（证明可用反证法）

第四种可能性: i’ 的回文半径与L压线

此时从 L 到 R 不用验，但是只有能不能扩的更大还需要再继续扩

由于：回文最右右边界R 只能往右推，不能往左缩，即：直接扩成功，R都在增加，R最多也就是从字符串左推到右，由于可能性2和3不用计算，直接知道答案，时间复杂度O(1)；因此只有可能性1与4 的代价使R从最左到最右，所以总时间复杂度为O（n），

最后附上代码：

public class Manacher {

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

	public static int maxLcpsLength(String str) {
		if (str == null || str.length() == 0) {
			return 0;
		}
		char[] charArr = manacherString(str);
		int[] pArr = new int[charArr.length];
		int index = -1;
		int pR = -1;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i != charArr.length; i++) {
			pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
					pArr[i]++;
				else {
					break;
				}
			}
			if (i + pArr[i] > pR) {
				pR = i + pArr[i];
				index = i;
			}
			max = Math.max(max, pArr[i]);
		}
		return max - 1;
	}

	public static void main(String[] args) {
		String str1 = "abc1234321ab";
		System.out.println(maxLcpsLength(str1));
	}
}
           

Manacher算法就是这样子的哦~~