自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 22:27:24，当前版本为作者最后更新于2023-09-20 21:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7180 [BOI2004] REPEATS

题意：给定字符串，求重复次数最多的连续重复子串。

考虑枚举这个子串的长度 $k$。如果 $lcp(suf(i), suf(i+k))=x$，那么则 $s_{[i,i+k-1]}$ 重复了 $\lfloor \dfrac{x}{k}\rfloor$ 次。那么我们就得到了一个 $O(n^2)$ 的做法，即先枚举 $k$，再枚举 $i$。

考虑优化，其实我们并不需要枚举所有的 $i$。容易发现如果 $[i,i+k-1]$ 与 $[j,j+k-1]$ 有交的话，计算一个向两侧的 lcp 即可。具体地，若计算 $i$，令 $l=i-1-lcs(pre(i+k-1), pre(i-1))+1$，$r=i+k+lcp(suf(i), suf(i+k))-1$，答案用 $\lfloor \dfrac{r-l+1}{k}\rfloor$ 更新。这样我们只用枚举 $i=1,1+k,1+k*2,...$。

lcp 和 lcs（反串 lcp）可使用后缀数组求解。

复杂度为 $O(n\log n+\dfrac n1 +\dfrac n2+...+\dfrac nn)=O(n\log n)$。

//P7180
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int t, n, a[N], lg2[N];
int sa[N], rk[N], cn[N], pr[N], he[N];
int st[N][20], stt[N][20];
int saa[N], rkk[N], hee[N];

void initial(){
	memset(sa, 0, sizeof(sa));
	memset(rk, 0, sizeof(rk));
	memset(cn, 0, sizeof(cn));
	memset(pr, 0, sizeof(pr));
	memset(he, 0, sizeof(he));
}
void suftech(){
	int m = 26;
	for(int i = 1; i <= n; ++ i){
		rk[i] = a[i];
		++ cn[rk[i]];
	}
	for(int i = 2; i <= m; ++ i){
		cn[i] += cn[i-1];
	}
	for(int i = n; i >= 1; -- i){
		sa[cn[rk[i]]--] = i;
	}
	for(int k = 1; k <= n; k <<= 1){
		int tot = 0;
		for(int i = n - k + 1; i <= n; ++ i){
			pr[++tot] = i;
		}
		for(int i = 1; i <= n; ++ i){
			if(sa[i] > k){
				pr[++tot] = sa[i] - k;
			}
		}
		for(int i = 1; i <= m; ++ i){
			cn[i] = 0;
		}
		for(int i = 1; i <= n; ++ i){
			++ cn[rk[i]];
		}
		for(int i = 2; i <= m; ++ i){
			cn[i] += cn[i-1];
		}
		for(int i = n; i >= 1; -- i){
			sa[cn[rk[pr[i]]]--] = pr[i];
			pr[i] = 0;
		}
		swap(rk, pr);
		tot = 1;
		rk[sa[1]] = 1;
		for(int i = 2; i <= n; ++ i){
			if(pr[sa[i]] == pr[sa[i-1]] && pr[sa[i]+k] == pr[sa[i-1]+k]){
				rk[sa[i]] = tot;
			} else {
				rk[sa[i]] = ++ tot;
			}
		}
		if(tot == n){
			break;
		}
		m = tot;
	}
	int k = 0;
	for(int i = 1; i <= n; ++ i){
		if(rk[i] == 1){
			he[rk[i]] = 0;
		}
		if(k){
			-- k;
		}
		int j = sa[rk[i]-1];
		while(i+k <= n && j+k <= n && a[i+k] == a[j+k]){
			++ k;
		}
		he[rk[i]] = k;
	}
	
	for(int i = 1; i <= n; ++ i){
		st[i][0] = he[i];
	}
	for(int i = 1; i <= lg2[n]; ++ i){
		for(int j = 1; j + (1<<i) - 1 <= n; ++ j){
			st[j][i] = min(st[j][i-1], st[j+(1<<(i-1))][i-1]);
		}
	}
}

int ask(int l, int r){
	if(l > r){
		swap(l, r);
	}
	++ l;
	int k = lg2[r - l + 1];
	return min(st[l][k], st[r-(1<<k)+1][k]);
}
int askk(int l, int r){
	if(l > r){
		swap(l, r);
	}
	++ l;
	int k = lg2[r - l + 1];
	return min(stt[l][k], stt[r-(1<<k)+1][k]);
}

int main(){
	lg2[0] = -1;
	for(int i = 1; i <= 50000; ++ i){
		lg2[i] = lg2[i>>1] + 1;
	}
	scanf("%d", &n);
	int ans = 0, lee, stp;
	for(int i = 1; i <= n; ++ i){
		static char ch[5];
		scanf("%s", ch);
		a[i] = ch[0] - 'a' + 1;
	}
	initial();
	suftech();
	reverse(a + 1, a + n + 1);
	memcpy(stt, st, sizeof(st));
	memcpy(saa, sa, sizeof(sa));
	memcpy(rkk, rk, sizeof(rk));
	memcpy(hee, he, sizeof(he));
	initial();
	suftech();
	for(int len = 1; len <= n; ++ len){
		for(int st = 1; st + len - 1 <= n; st += len){
			int r = st + len + askk(rkk[st], rkk[st+len]) - 1;
			int l = st - 1 - ask(rk[n-(st+len-1)+1], rk[n-(st-1)+1]) + 1;
			if(ans < (r-l+1) / len){
				ans = (r-l+1) / len;
				lee = len;
				stp = l;
			}
		}
	}
	printf("%d\n%d\n%d\n", ans, lee, stp);
	return 0;
}