milk patterns(后缀数组，lcp，k重复).cpp

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

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

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

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

	int k;
	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];
int get_lcp()
{
	int i,j,k;
	
	for(i=0,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(num[i+k] == num[j+k]) {
				k ++;
			}
			h[ Rank[i] ] = k;
		}
	}
	/*
	for(i=0;i<n;i++) {
		for(j=SA[i];j<n;j++) {
			printf("%d ", num[j]);
		}
		printf("* rank = %d, height = %d\n", Rank[SA[i]], h[i]);
	}
	puts("-----------");
	*/
	int ret = 0;
	kk --;
	for(i=0;i<n-kk;i++) {
		int t = INT_MAX;
		for(j=0;j<kk;j++) {
			t = min(t, h[i+j]);
		}
		ret = max(t, ret);
	}
	return ret;
}

int main()
{
	int i,j;
	while(scanf("%d %d", &n,&kk)==2) {
		nmax = -1;
		for(i=0;i<n;i++) {
			scanf("%d", num+i);
			nmax = max(nmax, num[i]);
		}
		num[n ++] = -1;
		make_sa();
		printf("%d\n", get_lcp());
	}
}