【POJ】1743 Musical Theme

时间：2023-03-09 15:40:51
【POJ】1743 Musical Theme

http://poj.org/problem?id=1743

题意：不可重叠最长重复子串，n<=20000，具体看《后缀数组》-- 罗穗骞

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=20015;

void sort(int *x, int *y, int *sa, int n, int m) {

	static int c[N], i;

	for(i=0; i<m; ++i) c[i]=0;

	for(i=0; i<n; ++i) c[x[y[i]]]++;

	for(i=1; i<m; ++i) c[i]+=c[i-1];

	for(i=n-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i];

}

void hz(int *r, int *sa, int n, int m) {

	static int t1[N], t2[N];

	static int *x, *y, *t, j, i, p=0;

	x=t1; y=t2;

	for(i=0; i<n; ++i) x[i]=r[i], y[i]=i;

	sort(x, y, sa, n, m);

	for(j=1, p=1; p<n; j<<=1, m=p) {

		p=0;

		for(i=n-j; i<n; ++i) y[p++]=i;

		for(i=0; i<n; ++i) if(sa[i]-j>=0) y[p++]=sa[i]-j;

		sort(x, y, sa, n, m);

		for(t=x, x=y, y=t, x[sa[0]]=0, p=1, i=1; i<n; ++i)

			x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++;

	}

}

void geth(int *a, int *sa, int *rank, int *h, int n) {

	static int k, i, j; k=0;

	for(i=1; i<=n; ++i) rank[sa[i]]=i;

	for(i=1; i<=n; h[rank[i++]]=k)

		for(k?--k:0, j=sa[rank[i]-1]; a[i+k]==a[j+k]; ++k);

}

const int oo=~0u>>2;

int sa[N], rank[N], h[N], n, a[N];

bool check(int k) {

	int mx=sa[1], mn=sa[1];

	for(int i=2; i<=n; ++i) {

		if(h[i]>=k) {

			mx=max(mx, sa[i]);

			mn=min(mn, sa[i]);

			if(mx-mn>=k) return 1;

		}

		else mx=sa[i], mn=sa[i];

	}

	return 0;

}

int main() {

	while(scanf("%d", &n), n) {

		scanf("%d", &a[1]); --n;

		for(int i=1; i<=n; ++i) scanf("%d", &a[i+1]), a[i]=a[i+1]-a[i]+100;

		hz(a, sa, n+1, 200);

		geth(a, sa, rank, h, n);

		int mid, l=0, r=n/2;

		while(l<=r) {

			mid=(l+r)>>1;

			if(check(mid)) l=mid+1;

			else r=mid-1;

		}

		if(l>=5) printf("%d\n", l);

		else puts("0");

	}

	return 0;

}

　　

经典题....我们求出height数组后，按二分的大小k分组。即每个组里的height值都要>=k，然后看每个块是否有sa值之差>=k的即可

（吐槽：poj不能用bits/stdc++.h啊啊啊啊啊啊ce了两发啊...

相关文章