神秘并查集做法 求条或证伪或hack

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

using namespace std;
using ll = long long;

const int N = 2e5 + 5;

int T, n, m, k, ans, cnt, mx;
int x[N], c[N], y[N], sa[N], rk[N], h[N], f[N], sz[N], id[N];
string s;

void Clear() {
	m = 'z';
	ans = -1;
	cnt = mx = 0;
	for (int i = 1; i <= max(n, m); i++) {
		c[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		x[i] = y[i] = sa[i] = rk[i] = h[i] = f[i] = sz[i] = id[i] = 0;
	}
	return ;
}

void Sort() {
	for (int i = 1; i <= n; i++) x[i] = s[i], c[x[i]]++;
	for (int i = 1; i <= m; i++) c[i] += c[i - 1];
	for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
	for (int k = 1; k < n; k <<= 1) {
		int p = 0;
		for (int i = n - k + 1; i <= n; i++) y[++p] = i;
		for (int i = 1; i <= n; i++) {
			if (sa[i] > k) y[++p] = sa[i] - k;
		}
		for (int i = 1; i <= m; i++) c[i] = 0;
		for (int i = 1; i <= n; i++) c[x[i]]++;
		for (int i = 1; i <= m; i++) c[i] += c[i - 1];
		for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
		swap(x, y);
		p = x[sa[1]] = 1;
		for (int i = 2; i <= n; i++) {
			if (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + k] != y[sa[i - 1] + k]) p++;
			x[sa[i]] = p;
		}
		m = p;
		if (n == m) return ;
	}
	return ;
} 

void Height() {
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; i++) {
		if (rk[i] == 1) continue;
		if(k) k--;
		int j = sa[rk[i] - 1];
		for (; i + k <= n && j + k <= n && s[i + k] == s[j + k]; k++) ;
		h[rk[i]] = k;
	}
	return ;
}

int Cmp(int a, int b) {
	return h[a] > h[b];
}

int Find(int x) {
	return f[x] == x ? x : f[x] = Find(f[x]);
}

void Merge(int x, int y) {
	int fx = Find(x), fy = Find(y);
	if (fx == fy) {
		return ;
	}
	if (sz[fx] > sz[fy]) {
		swap(fx, fy);
	}
	cnt -= sz[fy] == k;
	cnt -= sz[fx] == k;
	f[fx] = fy;
	sz[fy] += sz[fx];
	cnt += sz[fy] == k;
	return ;
}

void Solve() {
	Clear();
	cin >> s >> k;
	n = s.size();
	s = '#' + s;
	Sort(); 
	Height();
	for (int i = 1; i <= n; i++) {
		id[i] = f[i] = i, sz[i] = 1;
	}
//	cout << "------\n";
//	for (int i = 1; i <= n; i++) {
//		cout << sa[i] << ' ' << h[i] << '\n';
//	}
	sort(id + 1, id + 1 + n, Cmp); 
//	cout << "------\n";
//	for (int i = 1; i <= n; i++) {
//		cout << id[i] << ' ' << h[id[i]] << '\n';
//	}
	for (int i = n, j = 1; i >= 1; i--) {
		cnt += sz[n - i + 1] == k;
		for (; j <= n && h[id[j]] >= i; j++) Merge(id[j] - 1, id[j]);
		if (cnt > mx) {
			mx = cnt;
			ans = i;
		}
//		cout << cnt << ' ' << j - 1 << '\n';
	} 
	cout << ans << '\n';
	return ;
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for (cin >> T; T--; Solve()) ;
	return 0;
}