Hash 能做吗?为什么样例过不了?
查看原帖
Hash 能做吗?为什么样例过不了?
1383883
cqbzlyh楼主2025/7/2 09:10
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 250010;
const ull mod1 = 1000000009;
const ull base1 = 131;
const ull mod2 = 998244353;
const ull base2 = 13331;
ull h1[N], h2[N], p1[N];
ull h3[N], h4[N], p2[N];
int s1[N], s2[N];
int n;
void init_hash(int s[], ull h1[], ull h2[], ull p1[], ull p2[]) {
	p1[0] = p2[0] = 1;
	h1[0] = h2[0] = 0;
	for (int i = 1; i <= n; i++) {
		h1[i] = (h1[i - 1] * base1 + s[i]) % mod1;
		h2[i] = (h2[i - 1] * base2 + s[i]) % mod2;
		p1[i] = (p1[i - 1] * base1) % mod1;
		p2[i] = (p2[i - 1] * base2) % mod2;
	}
}
bool check(int len, int n) {
	map<pair<ull, ull>, bool> mp;
	for (int i = 1; i + len - 1 <= n; i++) {
		ull v1 = (h1[i + len - 1] - h1[i - 1] * p1[len] % mod1 + mod1) % mod1;
		ull v2 = (h3[i + len - 1] - h3[i - 1] * p2[len] % mod2 + mod2) % mod2;
		mp[ { v1, v2 }] = 1;
	}
	for (int i = 1; i + len - 1 <= n; i++) {
		ull v1 = (h2[i + len - 1] - h2[i - 1] * p1[len] % mod1 + mod1) % mod1;
		ull v2 = (h4[i + len - 1] - h4[i - 1] * p2[len] % mod2 + mod2) % mod2;
		if (mp.count({ v1, v2 }))
			return 1;
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s1[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> s2[i];
	}
	init_hash(s1, h1, h3, p1, p2);
	init_hash(s2, h2, h4, p1, p2);
	int l = 1, r = n, ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid, n)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

求debug.

2025/7/2 09:10
加载中...