#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define Max 20005

int s[Max],sa[Max],suffix[2][Max],rank1[2][Max],*sk1,*sk2,*rk1,*rk2;
int h[Max],height[Max];
int n,k;
/*
int cmp(int a,int b)
{
	return s[a]<s[b];
}

int cmp1(int a,int b)
{
	if(rk1[a]<rk1[b])	return 1;
	if(rk1[a]>rk1[b])	return 0;
	return rk1[a+k]<=rk1[b+k];     // rk1[a]==rk1[b]
}*/

int cmp(const void *a,const void *b)
{
	return  s[*(int*)a]-s[*(int*)b];
}

int cmp1(const void *a,const void *b)
{
	if(rk1[*(int*)a]<rk1[*(int*)b])	return -1;
	if(rk1[*(int*)a]>rk1[*(int*)b])	return 1;
	return rk1[(*(int*)a)+k]-rk1[(*(int*)b)+k];     // rk1[a]==rk1[b]
}


int equal1(int ii,int i)
{
	if(rk1[ii]==rk1[i] && rk1[ii+k]==rk1[i+k])
		return 1;
	return 0;
}

int check(int num,int len)
{
	int sum=0,i,flage=0;
	for(i=1;i<=n;i++)  //&& n-i+1+sum>=len
	{
		while(  i<=n && height[i]>=len)
		{
			flage=1;
			sum++;
			i++;
		}
		if(flage) { sum++,flage=0; }
		if(sum>=num) return 1;
	}
	return  0;
}

int b_f(int num,int r)
{
	int l=1,mid,temp;
	while(l<=r)
	{
		mid=(l+r)>>1;
		temp=check(num,mid);
		if(temp)	l=mid+1;
		else		r=mid-1;
	}
	return r;
}

int main()
{
	int i, *tempp,front,j,kk;
	while(scanf("%d%d",&n,&kk)!=EOF)
	{
		memset(suffix,0,sizeof(suffix));	
		memset(rank1,0,sizeof(rank1));
		memset(h,0,sizeof(h));
		sk1=suffix[0],sk2=suffix[1];
		rk1=rank1[0],rk2=rank1[1];

		for(i=1;i<=n;i++)	scanf("%d",&s[i]);
		s[++n]=-1;
		for(i=1;i<=n;i++) sk1[i]=i;
//		sort(sk1,sk1+n+1,cmp);	
		qsort(sk1+1,n,sizeof(int),cmp);
		for ( i = 1, j = 1; i<=n; i++) 
		{
			if (i>1 && s[sk1[i]]!=s[sk1[i-1]])  j++;
			rk1[sk1[i]] = j;
		}

		for(i=1;i<=n;i++)	sk2[i]=i;	
		for(k=1;rk1[ sk1[n] ]<n;k=k*2)       ///  rk1[ sk1[n] ]<n 最后一名的排名＞＝n时表明已经求出
		{                                                          
	//			sort(sk2+1,sk2+n+1,cmp1); 
			qsort(sk2+1,n,sizeof(int),cmp1);
				for ( i = 1, j = 1; i<=n; i++) 
				{
					if (i>1 &&  !equal1(sk2[i],sk2[i-1]) )  j++;
					rk2[sk2[i]] = j;
				}
			    tempp=sk1,sk1=sk2,sk2=tempp;
				tempp=rk1,rk1=rk2,rk2=tempp;
		}

		for(i=1;i<=n;i++)
		{
			if(rk1[i]==1)	h[i]=0;
			else
			{
				if(i==1 || h[i-1]<=1)	j=i,front=sk1[ rk1[i]-1 ];  // front (排名在 前面的串 的起始位置)
				else                 	j=i+h[i-1]-1,front=sk1[ rk1[i]-1 ]+h[i-1]-1;  //
				for( ;j<=n&& front<=n;j++,front++)
					if(s[front]!=s[j])	break;
				h[i]=j-i;  // 有三种情况 1：j和front都小于等于n  2: j超出n 3:front超出n
			}
		}
		for(i=1;i<=n;i++)
			height[rk1[i]]=h[i];
/*		for(i=1;i<=n;i++)
		{
			for(front=sk1[i];front<=n;front++)
				printf("%d ",s[front]);
			printf("\n");
		}
		for(i=1;i<=n;i++)
			printf("%d ",height[i]);
		printf("height\n");       
*/
		if(n==1)
			printf("1\n");
		else
			printf("%d\n",b_f(kk,n));
	}
	return 0;
}

• 你拿去自己拍一下吧 (2058) liyuliang001 2009-01-24 16:22:54