1 问题引入

给定一个长度为 \(n\) 的字符串 \(s\)，请找出该字符串中所有的回文子串。

显然对于一个长度为 \(n\) 的字符串，其回文子串至多有 \(n^2\) 个，因此如果一个个统计复杂度必定不会优秀。

那如何优化复杂度呢？这就要提到 Manacher 算法了。在探讨这个算法之前，我们需要先了解其基本的描述回文串的思路。

2 基本思想及暴力算法

2.1 基本思想

考虑对于回文串 \(s[i,j]\)，我们人为规定它的回文中心就是 \(\lfloor\dfrac{i+j+1}2\rfloor\)。也就是说，奇数长度的回文串的中心就是最中间的字符，而偶数长度的回文串的中心是中间靠右的字符。现在我们需要求出两个数组 \(d_1[i]\) 和 \(d_2[i]\)，分别表示 \(i\) 作为奇数长度回文串中心和偶数长度回文串中心时回文串的个数。

例如在字符串 abababc 中，\(d_1[4]\) 就等于 \(3\)，因为以它为中心的奇数长度回文串共有 b，aba，babab 三个。根据这个例子我们也可以看出，两个数组其实也表示以 \(i\) 为中心最长的回文串的半径长度（指的是从 \(i\)i 到回文串最右端的字符个数）。

那么如果我们有了 \(d_1[i]\) 和 \(d_2[i]\) 两个数组，将所有的值加起来就可以得到最后的结果了。

似乎这两个数组的求解也并不容易，于是接下来的问题就是怎样快速求出这两个数组。

2.2 暴力算法

显然在看到上面的定义后我们会立刻想到这样一种朴素的思路：对于每个 \(i\)，向两边枚举，直到两端不相同则停止，并将答案记录下来。

显然这个算法的时间复杂度为 \(O(n^2)\)，并没有跳脱我们上面提到的复杂度。而 Manacher 算法的任务就是：在线性时间复杂度之内，求出这两个数组。

3 Manacher 算法

3.1 算法过程

我们只以寻找奇数长度回文串为例说明，即只考虑数组 \(d_1[i]\)，因为 \(d_2[i]\) 的求解过程是类似的。

我们首先需要维护出一个最靠右的回文串的两个边界 \(l,r\)，初始设 \(l=1,r=0\)。

现在我们要计算 \(d_1[i]\)，而此时 \(1\sim i-1\) 的所有 \(d_1\) 全部计算完成。我们按照下面方法计算：

如果 \(i\) 不在当前回文串之内，即 \(i>r\)，直接调用暴力算法求解。
如果 \(i\) 在当前回文串之内，即 \(i\le r\)：

考虑在当前回文串中 \(i\) 的对称字符 \(j=l+r-i\)。现在由于 \(i\) 与 \(j\) 对称，那么我们可以说 \(d_1[i]=d_1[j]\)。可以认为我们是将以 \(j\) 为中心的回文串拷贝到以 \(i\) 为中心的回文串。

但是并不是每一种情况都可以这样做。如果以 \(j\) 为中心的回文串的左端点超出了当前回文串的左端点 \(l\)，即 \(j-d_1[j]+1\le l\)，此时我们并不能断言 \(d_1[i]=d_1[j]\)。实际上，此时我们仅能保证在当前 \([l,r]\) 回文串之内的部分绝对是回文串，也就是说我们只能令 \(d_1[i]\) 为 \(r-i+1\)。接下来我们再次跑暴力算法以尝试扩展当前回文串。

最后需要注意的是，每次计算完 \(d_1[i]\) 之后需要更新值 \(l,r\)。

容易发现上面的算法其实多次运行了暴力算法，所以这个算法的时间复杂度并不直观。考虑这样的分析：每一次运行暴力算法都会使 \(r\) 增加 \(1\)，同时 \(r\) 不会减小，所以该算法的时间复杂度实际上为 \(O(n)\)。

当然我们上面只讲述了对于 \(d_1[i]\) 的求解过程，\(d_2[i]\) 的求解是同理的。不过我们有更加方便的做法。

考虑在原字符串中的每两个字符间（以及开头前和结尾后）加入一个其他字符，例如 abaab 变为 #a#b#a#a#b#，这样我们会发现，原先不管长为奇数的回文串（aba）还是长为偶数的回文串（baab），最后都变成了长为奇数的回文串（a#b#a 和 b#a#a#b）。于是在新字符串上我们只需要处理出一个 \(d\) 数组即可。

值得注意的是，原先回文串 S 在新字符串中会多计算一次 #S#，因此最后应将答案除以 \(2\)。更为具体的讲，关系为 \(d[i]=2d_1[i]=2d_2[i]+1\)。

3.2 应用

上面讲解的求解回文子串个数是 Manacher 的一个应用，而另一个经典应用就是求最长回文子串。

实际上这个问题我们并不陌生，在之前的哈希以及后缀数组的学习中都遇到过。那时我们采用的都是二分，复杂度为 \(O(n\log n)\)。而 Manacher 算法的复杂度则为 \(O(n)\)。

现在考虑对于每一个位置为对称中心的回文子串长度。当 \(i\) 是奇数长度回文子串中心时，长度应该为 \(2d_1[i]-1=d[i]-1\)；当 \(i\) 为偶数长度回文子串中心时，长度应该为 \(2d_2[i]=d[i]-1\)。

因此无论是什么情况，最长回文子串长度就是 \(d[i]-1\)，求出 \(\max\) 即为答案。

下面以【模板】manacher 为例，给出代码：

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 3e7 + 5;
const int Inf = 2e9;

string s;
int n;

string init(string s) {//给字符串中间加上 `#`
	string t = " #";
	for(int i = 0; i < s.size(); i++) {
		(t += s[i]) += '#';
	}
	return t;
}

int d[Maxn];
void manacher(string s) {
	int l = 1, r = 0;//初始化
	for(int i = 1; i <= n; i++) {
		int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);//这句话浓缩了上面讨论的三种情况
        //k 代表的是当前以 i 为中心的最大回文串长度
		while(s[i - k] == s[i + k]) k++;//暴力向外扩展
		d[i] = k--;//记录答案
        //注意这里减一是为了减去跳出 while 多出来的字符
		if(i + k > r) {//更新 l,r
			l = i - k, r = i + k;
		} 
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	s = init(s);
	n = s.size() - 1;
	manacher(s);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = max(ans, d[i]);
	}
	cout << ans - 1;//注意最后要减一
	return 0;
}

标签：int,Manacher,复杂度,算法,长度,回文
From： https://www.cnblogs.com/dzbblog/p/18250635

Manacher