musical theme(后缀数组，lcp，二分枚举).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 25000;
int n, note[MAX], nmax;
int mem[3][MAX], c[MAX];
int * SA, * Rank, * nRank, * nSA;

void make_sa()
{
	int i,j,k;
	SA = mem[0]; Rank = mem[1]; nSA = mem[2];
	memset(c,0,sizeof(c));
	for(i=0;i<n;i++) {
		c[ note[i] ] ++;
	}
	for(i=1;i<=nmax;i++) {
		c[i] += c[i-1];
	}
	for(i=0;i<n;i++) {
		SA[ --c[ note[i] ] ] = i;
	}
	Rank[ SA[0] ] = 0;
	for(i=1;i<n;i++) {
		Rank[SA[i]] = Rank[SA[i-1]];
		if(note[SA[i]] != note[SA[i-1]]) {
			Rank[SA[i]] ++;
		}
	}

	for(k=1;k<n && Rank[SA[n-1]] < n-1;k*=2) {
		memset(c,0,sizeof(c));
		for(i=0;i<n;i++) {
			c[Rank[SA[i]]] ++;
		}
		for(i=1;i<n;i++) {
			c[i] += c[i-1];
		}
		for(i=n-1;i>=0;i--) {
			if(SA[i] >= k) {
				nSA[ --c[ Rank[SA[i]-k] ] ] = SA[i] -k;
			}
		}
		for(i=n-k;i<n;i++) {
			nSA[ --c[Rank[i]] ] = i;
		}

		nRank = SA;
		nRank[ nSA[0] ] = 0;
		for(i=1;i<n;i++) {
			nRank[nSA[i]] = nRank[nSA[i-1]];
			if(Rank[nSA[i]] != Rank[nSA[i-1]] || Rank[nSA[i]+k] != Rank[nSA[i-1]+k]) {
				nRank[nSA[i]] ++;
			}
		}
		SA = nSA;
		nSA = Rank;
		Rank = nRank;
	}
}

int h[MAX];
bool check(int len)
{
	int i,j;
	int lmin;
	for(i=0;i<n;i++) {
		if(h[i] >= len) {
			lmin = h[i];
			int s = SA[i];
			for(j=0; i+j < n-1 ;j++) {
				lmin = min(lmin, h[i+j]);
				if(lmin < len) {
					break;
				}
				int t = s + lmin-1;
				int s2 = SA[i+1+j];
				int t2 = s2 + lmin-1;
				if(t < s2 || t2 < s) {
					return true;
				}
			}
		}
	}
	return false;
}

int get_lcp()
{
	int i,j,k;
	for(i=k=0;i<n;i++) {
		if(Rank[i] == n-1) {
			h[Rank[i]] = k = 0;
		}
		else {
			if(k > 0) {
				k --;
			}
			j = SA[ Rank[i] +1];
			while(note[i+k] == note[j+k]) {
				k ++;
			}
			h[ Rank[i] ] = k;
		}
		h[Rank[i]] ++;
	}
	int l = 0, r = n-1;
	while(l < r) {
		int mid = (l+r+1)/2;
		if(check(mid)) {
			l = mid;
		}
		else {
			r = mid -1;
		}
	}
	return l >= 5 ? l : 0;
}

int main()
{
	int i, pre, now, nmin;
	while(scanf("%d", &n), n) {
		nmin = INT_MAX;
		scanf("%d", &pre);
		//difference sequence
		for(i=0;i<n-1;i++) {
			scanf("%d", &now);
			note[i] = now - pre;
			pre = now;
			nmin = min(nmin, note[i]);
		}
		n --;
		nmax = 0;
		for(i=0;i<n;i++) {
			note[i] += -nmin+1;
			nmax = max(nmax, note[i]);
		}
		note[n ++] = 0;//special end
		make_sa();
		printf("%d\n", get_lcp());
	}
}