进行一个字符串算法的总结

本文参考 字符串基础 by Alex_Wei。

Manacher 算法

这玩意是用来求回文子串的。

虽然一个字符串的子串数量是 \(O(n^2)\) 级别的，但是回文串有更好的描述方式。

注意到若一个子串 \([l, r]\) 是以 \(mid\) 为回文中心的回文串，那么将左端点和右端点朝着 \(mid\) 方向挪动若干单位也是回文串。因此我们只需要记录回文中心和最大的回文半径就可以得到所有回文子串的信息。

回文中心的个数是 \(O(n)\) 级别的，所以能高度压缩地记录回文串的信息。

Manacher 算法就是一个 \(O(n)\) 的时间复杂度求出每个点的回文半径的算法。

随便敲个字符串 \(\texttt {aazuusuuzazza}\) 出来。

观察到偶数长度的回文子串的回文中心在两个字符之间，而奇数长度的回文子串回文中心是一个字符。

为了把这两种子串统一起来，我们在两个字符之间加入一个不会在串中出现的字符，例如 \(\texttt{@}\)。

然后我们得到了串串 \(\texttt {@a@a@z@u@u@s@u@u@z@a@z@z@a@}\)。

设 \(R_i\) 为新串的第 \(i\) 个字符的最长回文半径，那么我们要求的是 \(R\) 数组。

手玩一下，以第 \(i\) 个字符为回文中心的最长串串的长度就是 \(R_i - 1\)。

考虑一种暴力。枚举回文中心后尝试向两边扩展，能扩展则扩展。

因为回文串级别是 \(O(n^2)\) 的，所以这个算法的时间复杂度是 \(O(n^2)\) 的。

但是我们发现回文串有些比较好的性质。

举个例子，我们在上面抓个子串出来。就决定是你了，\(\texttt {@a@a@z@u@u@s@u@u@z@a@z@}\)。

假设我们已经知道了最中间的那个 \(\texttt{s}\) 的 \(R_i\) 是 \(10\)，能扩展到最远的地方是倒数第二个 \(\texttt @\)。

再考虑这个 \(\texttt s\) 后面三个字符的那个 \(\texttt @\)。我们的 \(R_i\) 还用从 \(0\) 开始枚举吗？

把这个 \(\texttt @\) 对称过去，找到 \(\texttt s\) 前面三个的 \(\texttt @\)。我们求出了这个 \(\texttt @\) 的最长回文半径是 \(3\)。

那对称地，这个 \(\texttt @\) 的最长回文半径至少是 \(3\)，这样我们将 \(R_i\) 赋初始值为 \(3\) 就行了。

再考虑倒数第四个字符的那个 \(\texttt a\)。对称过去是第二个字符的 \(\texttt a\)，其 \(R\) 为 \(2\)，所以赋这个 \(a\) 初值为 \(2\)。这个时候就能继续扩展到 \(4\)。然后能扩展到最远的地方更远了，所以更新当前对称中心和扩展到的最远地方。

实现上，设当前扩展到最远的地方为 \(r\)，对称中心为 \(c\)。

如果当前字符 \(i > r\)，那么令 \(R_i = 0\)。否则令 \(R_i = \min\{R_{2c - i}, r - i + 1\}\)。

然后暴力扩展，更新 \(r\) 和 \(c\)。

对于每个 \(r\)，在 \(i < r\) 的时候更新是 \(O(1)\) 的，而 \(r\) 最多变化 \(n\) 次。

所以时间复杂度是 \(O(n)\) 的。

P3805 【模板】manacher

把 \(R\) 数组求出来后对 \(R_i - 1\) 求 \(max\) 即可。

namespace azus{
	int n;
	string s, a;
	int R[23000005];
	int main(){
		cin >> s;
		n = s.length();
		for(int i = 0; i < n; i ++)
			a += "@", a += s[i];
		a = a + "@"; n = a.length(); a = " " + a;
		R[1] = 1;
		int r = 1, c = 1, ans = 0;
		for(int i = 1; i <= n; i ++){
			if(i <= r)
				R[i] = min(r - i + 1, R[2 * c - i]);
			while(i - R[i] >= 0 && i + R[i] <= n && a[i - R[i]] == a[i + R[i]])	R[i] ++;
			if(i + R[i] - 1 > r) r = i + R[i] - 1, c = i;
			ans = max(ans, R[i] - 1);
		}
		cout << ans;
		return 0;
	}
}

意外的发现 a += "@" 和 a = a + "@" 有很大区别，前者复杂度 \(O(1)\)，后者还要加上复制串串的复杂度所以是 \(O(n)\)。

P3501 [POI2010] ANT-Antisymmetry

和回文串性质一样，在 while 循环中改改条件，变成扩展 ANT-Antisymmetry 串就行了。

P4555 [国家集训队] 最长双回文串

对于每个 \(\texttt @\)，统计以它为右端点的最长回文串和以它为左端点的最长回文串。

但是我们统计的 \(R_i\) 是一个点能扩展到的最长长度。

定义一个回文串是饱和的，如果这个字符串不能再扩展了。我们发现有些点结尾或开头的不饱和字符串比包和字符串还长。

所以简单递推更新一下即可。

//Manacher 中
ls[i + R[i] - 1] = max(ls[i + R[i] - 1], R[i] - 1);
rs[i - R[i] + 1] = max(rs[i - R[i] + 1], R[i] - 1);
//进行一个简单递推和统计方案
for(int i = n; i >= 3; i -= 2)
	ls[i] = max(ls[i + 2] - 2, ls[i]);
for(int i = 3; i <= n; i += 2)
	rs[i] = max(rs[i - 2] - 2, rs[i]);
for(int i = 1; i <= n; i ++)
	if(a[i] == '@' && ls[i] && rs[i]) ans = max(ans, ls[i] + rs[i]);

P1659 [国家集训队] 拉拉队排练

把每个长度的奇回文串的长度用桶统计一下。

然后用快速幂直接做就行了。

for(int i = 2; i <= n; i += 2)
	t[R[i] - 1] ++;
for(int i = n - (!(n & 1)); i >= 1; i --){
	if(!t[i]) continue;
	if(k <= t[i]) {ans = ans * ksm(i, k) % P, k = 0; break;}
	if(i == 1) break;
	k -= t[i], ans = ans * ksm(i, t[i]) % P;
	t[i - 2] += t[i], t[i] = 0;
}

P5446 [THUPC2018] 绿绿和串串

这东西乍看下去有点复杂。

观察下，首先发现如果有一个以最后一个字符结尾的回文子串，那么以这个子串回文中心翻转一下一定满足条件。

然后，如果以 \(i\) 为轴翻转的串满足条件，那么如果有个字符串能翻转造出字符串 \([1, i]\) 那也能满足条件。

这个字符串必须从 \(1\) 开始翻转，所以这个字符串的回文中心固定为 \(\frac 12 (1 + i)\) 这个位置。

从后往前递推判断每个字符是否能满足条件即可。

//Manacher 中
if(a[i] != '@' && i + R[i] - 1 == n) flg[i] = 1;
//进行一个递推
for(int i = n - 1; i >= 2; i -= 2){
	if(flg[i]){
		int u = 1 + (i + 1) / 2;
		if(a[u] == '@') continue;
		if(u + R[u] - 1 == i + 1) flg[u] = 1;
	}
}
for(int i = 1; i <= n; i ++)
	if(flg[i]) cout << i / 2 << " ";