Manacher算法（施工中）

问题描述

Manacher算法是一种用来寻找最长回文子串的算法。首先，什么是最长回文子串？

回文：当一个串正序和倒序遍历结果完全一致时，称之为回文串。如abcba、bddb

子串：当一个字符串是另一个串的一部分时，称之为子串

最长：所谓“最长回文子串”，就是所有的“回文子串”中长度最大的那一个或多个。

必要的简化

回文串可以分为两种，“abcba”这种“中心对称”的（因为有一个对称轴c）和“bddb”这种没有对称轴的。接下来我们首先研究如何寻找第一种回文串。

寻找“中心对称”回文子串的Manacher算法

先从O(N²)的暴力做法说起……

我们要寻找的是有对称轴的回文串，因此我们可以分别考虑串中每一个位置（一共N个）为对称轴的情况，从该位置向左右两侧逐渐“扩张”，即可找到全部的回文子串。

for (int i = 0;i < n;++i) {
	for (int j = 0;j < n && i - j >= 0 && i + j < n;++j) { // 此处防止下标越界
		if (arr[i-j] == arr[i+j]) {
			continue;
		}
		else {
			break;
		}
	}
	// 此时的j即为i为对称轴的回文子串最大长度，对这个存储并进行max即可
	radii[i] = j;
}

由于一共有n个位置，每次扩张能够成功的次数又与n成正比，因此时间复杂度为O(N²)。

信息就是资源，而我们有多余的信息

刚才我们选择了最直觉的方法解决问题。然而，注意力好的同学已经注意到了，如果我们照着这个算法执行存在多余的信息。假设有串：

dacabacad

我们第一次成功“扩张”会是在此处：

dacabacad

第二次成功“扩张”：

dacabacad

这时候我们已经知道字符b左边的4个字符与b右边的四个字符是相等的，那么我们就已经知道右边的字符c为对称轴时的对称半径也为1：

dacabacad

但是，如果按这个算法执行，却需要对右边的c重新进行一次成本至多为N的“扩张”操作。这也是O(N²)里第二个N的来源。

这里有多余的信息可以利用！

“已知”的边界

在上面的例子中，我们以b为中心进行扩张的时候，其实直到右边的字符d为止，都已经被遍历过了，我们此时已经有了到这个字符d为止的全部信息！

dacabacad

因此，最好的可能是我们不需要在d之前的范围内做任何“扩张”操作。此时，这个d即是已知信息的边界。

我们记录一个当前的已知边界r，以及产生这个r时的对称轴axis。

当我们在为一个axis右边的位置i试图进行“扩张”操作得到其回文半径时，会有两种情况：

我们最终扩张的结果不会超过right。这种情况下，我们进行扩张全程不会用到right以外的信息就遇到了一次匹配失败。那其实我们可以按照axis找到它的对称点2*axis - i，该位置的半径radii[2*axis - i]即是radii[i]的值。这种情况的条件为radii[2*axis - i] + i < r。
我们最终的扩张结果超过了right。这种情况下，我们进行扩张时会一直成功，直到越过了r，而r外面的部分不曾被访问、我们必然对其一无所知，此时我们就不得不进行实际的扩张了。这种情况的条件为radii[2*axis - i] + i >= r。需要注意的是，这里即使radii[2*axis - i] + i大于了r，也不能让我们真的获得r以外的信息，因此还是需要从位置r+1开始判断。

综上所述，我们其实只需要做一件事，就能利用上全部多余信息了：每次执行扩张之前，查看radii[2*axis - i]和r-i的最小值，并以这个值当做i已知的半径开始扩张，而不是从0开始扩张：

for (int i = 0;i < n;++i) {
	int j = 0;
	if ( 2*axis - i >= 0 && i<=j) { 
		j = min(radii[2*axis - i], r - i);
	}
	for (;j < n && i - j >= 0 && i + j < n;++j) { // 此处防止下标越界
		if (arr[i-j] == arr[i+j]) {
			continue;
		}
		else {
			break;
		}
	}
	// 此时的j即为i为对称轴的回文子串最大长度，对这个存储并进行max即可
	radii[i] = j;
	// 更新当前的已知边界
	if (i + j > r) {
		r = i + j;
		axis = i;
	}
}

我们每次执行实际的“扩张”操作，都能让已知的边界前进1步，而这个已知边界至多前进n步。至此，我们最大限度地利用了已知的信息，以O(N)的代价完成了目标！

另一种情况

现在我们已经知道，如何寻找“有对称轴”的子串了，那么无对称轴的那种呢？其实我们可以对整个串和子串都进行一种操作：每隔一个字符就插入一个原字符串中没有的占位符（如#），这样一来查找

“bddb”

就变成了查找

“#b#d#d#b#”

可以看到现在问题变成了寻找一个有对称轴的子串

这样就化归成了一个已知问题。

完整的代码实现

（出差手头没有环境，调试不了代码，先咕了）

结语

这是详解算法系列的第三期，我们介绍了莫里斯遍历、KMP算法和Manacher算法。它们要解决的问题描述无比清楚，只需要用到最基础的概念；而要理解这些算法本身也不需要了解多少额外的知识。单看题面，由于它是如此简单，以至于你会第一反应认为暴力法是唯一的解，那种更优的算法是不可能的。因此，得知了答案的存在后，令人难以忍耐把玩一番的冲动。

之所以以这几个作为开篇，不仅仅是因为它们很难，更是由于它们共同体现出的一种的精巧：它们都体现出了一种极端的渴求，对已知信息高效利用的渴求，将所有已知信息榨干出最后一滴价值，绝不浪费。

然而，现实中的问题不是产生在真空中的。我们能拿到的信息是不干净的，有些难以处理，有些可信存疑，有些则干脆是无用的干扰项。我们不得不对信息做出取舍，并抛弃掉其中的一部分（也许是大部分）。对于生活在“肮脏”信息流中的我们，能见到如此纯粹、干净的东西，的确是一种难得的享受啊。

今夜闻君琵琶语，如听仙乐耳暂明。