自动搬运

查看原文

来自洛谷，原作者为

	Jayun 乘骐骥以驰骋兮，来吾道夫先路！

搬运于2025-08-24 21:53:49，当前版本为作者最后更新于2021-05-12 13:50:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

链接：

洛谷

博客园

题目大意:

在一个圆环上从两个位置出发转圈圈，经过的位置随机变换，求环的最大长度。

正文：

假设我们以及知道了环的最大长度 $l$。由于这是一个环，所以 $A$ 串的部分一和 $B$ 串的部分二、$A$ 串的部分二和 $B$ 串的部分一必定相同：

一个串的第一部分在另一个串里找相同的第二部分的这个过程，就可以用扩展 KMP 实现。也就是两次扩展 KMP 的得到 $A$ 对于 $B$ 的 z 函数 $z_1(i)$，和 $B$ 对于 $A$ 的 z 函数 $z_2(i)$。现在考虑怎么通过这两个 z 函数求出答案。

设对于 $A$ 串，第一部分结尾在 $i$ 处；对于 $B$ 串，第二部分结尾在 $j$ 处。很容易得到 $i+j=l$，且 $z_1(i+1)\geq j,z_2(j+1)\geq i$。

由于对于每一个 $i$ 可以通过 $z_1(i+1)$ 得到 $j$ 的上界，于是可以通过树状数组维护 $j$，同时对于每一个 $i$ 也可以求出最大的合法的 $j$。

const int N = 4e6 + 10;

inline ll READ()
{
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n;
string a, b;
int z1[N], z2[N];

void exKMP(string s, int *z)
{
	int len = s.size(), l = 0;
	for (int i = 1; i < len; i++)
	{
		if (l + z[l] > i) z[i] = min(z[l] - i + l, z[i - l]);
		while (i + z[i] < len && s[z[i]] == s[z[i] + i]) z[i]++;
		if (i + z[i] > l + z[l]) l = i;
	}
}

vector <int> vec[N];
ll ans;
ll t[N];

void modify(int x)
{
	for (int i = x; i <= n; i += i & -i) t[i] = max(t[i], 1ll * x);
}
ll query(int x)
{
	ll ans = 0;
	for (int i = x; i; i -= i & -i) ans = max(t[i], ans);
	return ans;
}

int main()
{
	n = READ();
	cin >> a; cin >> b;
	exKMP(a + b, z1);
	exKMP(b + a, z2);
	for (int i = 1; i <= n; i++)            // 这里 z1[i]、z2[i] 的下标还是从一开始的
		z1[i] = z1[i + n - 1], z1[i + n - 1] = 0,
		z2[i] = z2[i + n - 1], z2[i + n - 1] = 0;
	for (int j = 1; j < n; j++)
		vec[z2[j + 1]].push_back(j);
	for (int i = n - 1; i; i--) 
	{
		for (int j : vec[i])
			modify(j);
		ll j = query(z1[i + 1]);
		if (j) ans = max(ans, i + j);
	}
	printf ("%lld\n", ans);
	return 0;
}