算法学习笔记(19): Manacher算法

简介:

Manacher算法用于解决找到所有回文子串的问题。例如：

给定一个长度为N的字符串s，找到所有的(i, j) 使得 s[i: j]是回文串。

问题思考

作为回文串，通常有一个中点，回文串是以这个中点对称的。

这个中点可能是一个字符，也可能是一个间隙。

以字符作为中点的字符串长度是奇数，以间隙作为中点的字符串长度是偶数。

如果要记录所有的回文子串：

我们不妨算出所有d1[i] 表示以第 i 个字符作为中心，最长的回文串长度。

我们不妨算出所有d2[i] 表示以第 i 个间隙作为中心，最长的回文串长度。

暴力朴素算法

对于每个中心我们都需要n次来判断，也就需要O(N2)的复杂度。

vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {
	  d1[i] = 1;
	  while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
		    d1[i]++;
	  }
	
	  d2[i] = 0;
	  while (0 <= i - d2[i] - 1 && i + d2[i] < n &&
	         s[i - d2[i] - 1] == s[i + d2[i]]) {
		    d2[i]++;
	  }
}

性质

对于一个回文串，例如 abcba，易得以s[2] = c 有 d[2] = 5。

如果我们有abacaba 可得

d[0 ~ 6] = [1, 3, 1, 7, 1, 3, 1]

如果一个字符串是回文的，那么它的d数组也一定回文，由对称性易证。

性质利用

当我们遇到 a b a c a b a c

当我们已经得出d[0 ~ 5], 当我们要计算 d[6]时，可得 d[6] 是 ≥ 3的

依据了以第一个 c 作为对称点 d[6] ≥ d[1] = 3;

所以对于d[6] 我们就不需要再从 1 开始计算，直接从 3 开始往后判断即可。

代码思路

对于以上性质的利用，我们从左往右地依次完成d数组内的数值。

我们使用两个变量l和r来保存一个回文串的位置，其中，这个回文串是用于使用以上性质的。因此每次保存的这个回文串是处理到当前位置中，r值最靠右的回文串。

先只考虑以字符作为中点的情况：

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
	  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
	  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
		    k++;
	  }
	  d1[i] = k--;
	  if (i + k > r) {
		    l = i - k;
		    r = i + k;
	  }
}

当目前计算的 i 不在记录的回文串内，说明我们无法使用性质，老老实实使用朴素算法，从 1 开始。
当目前计算的 i 在记录的回文串内，说明可以利用性质找到对称的值，但需要注意的是：虽然可以得到一个值，但是要确保不会超过边界，因此有 min(d1[l + r - i], r - i + 1) 。

同理：

vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
	  int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
	  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
		    k++;
	  }
	  d2[i] = k--;
	  if (i + k > r) {
		    l = i - k - 1;
		    r = i + k;
	  }
}

以上是关于间隙的。

其它

实际上也可以吧空隙作为一个字符，例如给一个空格作为符号，需要注意的是得到的长度答案也会变化，只不过也是固定的变化，1变成3，x 变成 2 x + 1。为了保证长度是1 的能变成 3，边缘两边也需要这个标记符号，然后根据d1的获取方法得到答案后，(d - 1) / 2 也就是原答案。

Mai Icy