题解：P13867 [SWERC 2020] Unique Activities

Sol

因为长度为

len

的子串满足，

\ge len

的也满足，发现重复子串的长度具有单调性，考虑二分答案。

在

\operatorname{check}

函数中，对长度为

len

的子串的哈希值进行统计，再检查是否有唯一的，若有，记录起始下标

st = i

。

Code

CPP

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 3e5 + 10, P = 13331;

string s;
int n, st;
ull hs[N], pw[N];
map<ull, int> mp;

ull get_hs(int l, int r) {
	return hs[r] - hs[l - 1] * pw[r - l + 1];
}

bool check(int mid) {
	if (mid == 0 || mid > n)
		return 0;
	mp.clear();
	for (int i = 1; i + mid - 1 <= n; i++) {
		int j = i + mid - 1;
		mp[get_hs(i, j)]++;
	}
	for (int i = 1; i + mid - 1 <= n; i++) {
		int j = i + mid - 1;
		if (mp[get_hs(i, j)] == 1) {
			st = i;
			return 1;
		}
	}
	return 0;
}

signed main() {
	cin >> s;
	n = s.size();
	s = ' ' + s;
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * P;
		hs[i] = hs[i - 1] * P + s[i];
	}
	int l = 0, r = n + 1;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	cout << s.substr(st, r);
	return 0;
}

题解：P13867 [SWERC 2020] Unique Activities

文章操作

Sol

Code

相关推荐

评论

题解：P13867 [SWERC 2020] Unique Activities