【TJOI2019】甲苯先生和大中锋的字符串

题目链接：https://www.luogu.com.cn/problem/P5341

题目大意：给定 (T) 个字符串, 分别求出这 (T) 个字符串中所有恰好出现 (k) 次的子串中 , 出现过最多次数的长度的最大值

solution

对每个字符串 , 先求出它的 (height) 数组

考虑恰好出现 (k) 次的子串 (s) , 对于 (height) 数组中连续的 (h[i] ... h[i + k - 1]) , 其必然满足 (len(s) < min left{h[i] , h[i + 1] , ... ,h[i + k - 1] ight}) , 同时 (s) 的出现次数不应超过 (k) , 因此 (len(s) > maxleft{h[i - 1] , h[i + k] ight}) , 不难看出对于每 (k) 个数 , 满足要求的 (s) 的长度一定连续 , 于是可以用差分进行区间加 , 统计各个长度出现的次数 , 最后遍历找出最大值即可

时间复杂度: (O(T imes nlogn))

code

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
	int RR = 1; FF = 0; char CH = getchar();
	for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
	for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
	FF *= RR;
}
inline void file(string str) {
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10;
int tax[N], n, m = 'z', rk[N], xt[N], sa[N], ht[N], ki, pre[N];
char ch[N];
void get_sa() {
	memset(tax, 0, sizeof(tax));
	for(int i = 0; i <= n; i++) ht[i] = rk[i] = xt[i] = sa[i] = 0;
	for(int i = 1; i <= n; i++) tax[rk[i] = ch[i]]++;
	for(int i = 1; i <= m; i++) tax[i] += tax[i - 1];
	for(int i = n; i >= 1; i--) sa[tax[rk[i]]--] = i;
	for(int k = 1; k <= n; k <<= 1) {
		int now = 0;
		for(int i = n - k + 1; i <= n; i++) xt[++now] = i;
		for(int i = 1; i <= n; i++)
			if(sa[i] > k) xt[++now] = sa[i] - k;
		for(int i = 1; i <= m; i++) tax[i] = 0;
		for(int i = 1; i <= n; i++) tax[rk[i]]++;
		for(int i = 1; i <= m; i++) tax[i] += tax[i - 1];
		for(int i = n; i >= 1; i--) sa[tax[rk[xt[i]]]--] = xt[i];
		swap(xt, rk); now = rk[sa[1]] = 1;
		for(int i = 2; i <= n; i++)
			rk[sa[i]] = xt[sa[i]] == xt[sa[i - 1]] && xt[sa[i] + k] == xt[sa[i - 1] + k] ? now : ++now;
		m = now; if(n == m) return;
	}
}
void get_height() {
	for(int i = 1; i <= n; i++) rk[sa[i]] = i;
	int j = 0;
	for(int i = 1; i <= n; i++) {
		if(rk[i] == 1) continue;
		if(j != 0) j--;
		while(i + j <= n && sa[rk[i] - 1] + j <= n && ch[sa[rk[i] - 1] + j] == ch[i + j]) j++;
		ht[rk[i]] = j;
	}
}
int main() {
	//file("");
	int T;
	read(T);
	while(T--) {
		cin >> ch + 1;
		n = strlen(ch + 1); m = 'z';
		get_sa(), get_height();
		cin >> ki; ht[n + 1] = ht[0] = 0;
		for(int i = 0; i <= n + 1; i++) pre[i] = 0;
		deque<int> qi; int ans = 0;
		for(int i = 1; i <= ki; i++) {
			while(!qi.empty() && ht[i] <= ht[qi.front()]) qi.pop_front();
			qi.push_front(i);
		}
 		for(int i = ki; i <= n; i++) {
 			if(i - qi.back() + 1 >= ki) qi.pop_back();
			while(!qi.empty() && ht[i] <= ht[qi.front()]) qi.pop_front();
			qi.push_front(i);
			int lmax = 0, lmin = max(ht[i + 1], ht[i - ki + 1]);
			if(ki == 1) lmax = n - sa[i + ki - 1] + 1;
			else lmax = ht[qi.back()];
			if(lmax > lmin) pre[lmin + 1]++, pre[lmax + 1]--;
		}
		for(int i = 1; i <= n; i++) pre[i] += pre[i - 1];
		for(int i = n; i >= 1; i--)
			if(pre[i] > pre[ans]) ans = i;
		if(ans == 0) ans = -1;
		cout << ans << endl;
	}
	return 0;
}