题目大意

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

正文

假设我们以及知道了环的最大长度 $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;
}