这个题用倍增算法有什么要注意的地方吗？我将各个sa和rank数组存放在一个二维数组里，总是超时。下面是我的代码。



#define NUM 100010
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int sa[20][NUM<<1],rank[20][NUM<<1],curlv,curlen;
int h[NUM<<1],height[NUM<<1];
char str[NUM*2+10];


int cmp(const void* a,const void* b)
{
	if(curlv==0) 
		return 	str[*(int*)a]-str[*(int*)b];
	else  if(rank[curlv-1][*(int*)a]==rank[curlv-1][*(int*)b])
		return rank[curlv-1][(*(int*)a)+curlen/2] - rank[curlv-1][(*(int*)b)+curlen/2];
	else
		return  rank[curlv-1][*(int*)a] - rank[curlv-1][*(int*)b];
}
bool isequal(int clv,int cln,int p1,int p2)
{
	if(clv==0)
		return str[p1]==str[p2];
	if(rank[clv-1][p1]==rank[clv-1][p2]&&
		rank[clv-1][p1+cln/2]==rank[clv-1][p2+cln/2])
		return true;
	return false;
}
void getsa()
{
	int i,r,len=strlen(str+1);
	for(curlv=0,curlen=1;curlen<len;++curlv,curlen*=2)
	{
		for(i=1;i<=len;++i)		sa[curlv][i]=i;
		qsort(sa[curlv]+1,len,sizeof(int),cmp);
		rank[curlv][sa[curlv][1]]=1;r=1;
		for(i=2;i<=len;++i)
		{
			if(!isequal(curlv,curlen,sa[curlv][i],sa[curlv][i-1]))
				++r;
			rank[curlv][sa[curlv][i]]=r;
		}
	}
}
int main()
{
	scanf("%s",str+1);
	int len=strlen(str+1),i;str[len+1]=1;
	scanf("%s",str+len+2);
	int left=len;
	len=strlen(str+1);
	getsa();
	for(i=1;i<=len;++i)
	{
		int j;
		int a=i;
		int b=sa[curlv-1][rank[curlv-1][i]-1];
		if(rank[curlv-1][i]==1) h[i]=0;
		else if(i==1||h[i-1]<=1)
		{
			for(j=0;str[a+j]==str[b+j];++j);
			h[i]=j;
		}
		else 
		{
			for(j=h[i-1]-1;str[a+j]==str[b+j];++j);
			h[i]=j;
		}
	}
	for(i=1;i<=len;++i)
		height[i]=h[sa[curlv-1][i]];
	int ans=0;
	for(i=2;i<=len;++i)
	{
		if(sa[curlv-1][i]<=left&&sa[curlv-1][i-1]>left || sa[curlv-1][i]>left&&sa[curlv-1][i-1]<=left)
			if(height[i]>ans) ans=height[i];
	}
	printf("%d\n",ans);
	return 0;
}

• Re:请教 (12) zfy0701 2008-09-17 01:47:03