疑问兼警示后人
查看原帖
疑问兼警示后人
817925
whileAK楼主2024/7/22 17:11

看以下代码:

void SA(int *sa,int *rk,int *ht,int st[][N]){
	memset(rk,0,sizeof(rk));//注意这里
	c[n+1]='&';
	for(int i(1);i<=26;++i)ct[i]=0;
	for(int i(1);i<=n;++i){
		ct[c[i]-'a'+1]=1;
	}
	for(int i(1);i<=26;++i)ct[i]+=ct[i-1];
	for(int i(1);i<=n;++i)rk[i]=ct[c[i]-'a'+1];
	m=ct[26];
	for(int i(1);i<=26;++i)ct[i]=0;
	for(int i(1);i<=n;i<<=1){
		for(int j(1);j<=n;++j)++ct[rk[j+i]];
		for(int j(1);j<=m;++j)ct[j]+=ct[j-1];
		for(int j(1);j<=n;++j)x[ct[rk[j+i]]--]=j;
		for(int j(1);j<=m;++j)ct[j]=0;
		for(int j(1);j<=n;++j)++ct[rk[x[j]]];
		for(int j(1);j<=m;++j)ct[j]+=ct[j-1];
		for(int j(n);j;--j)y[ct[rk[x[j]]]--]=x[j];
		for(int j(1);j<=m;++j)ct[j]=0;
		m=0;
		for(int j(1);j<=n;++j){
			if(rk[y[j]]!=rk[y[j-1]]||rk[y[j]+i]!=rk[y[j-1]+i])++m;
			x[y[j]]=m;
		}
		for(int j(1);j<=n;++j)rk[j]=x[j];
		if(m==n)break;
	}
	for(int i(1);i<=n;++i)sa[rk[i]]=i;
	for(int i(1),k(0);i<=n;++i){
		if(rk[i]==1){ht[rk[i]]=0;st[0][rk[i]]=0;continue;}
		if(k)--k;
		while(c[i+k]==c[sa[rk[i]-1]+k])++k;
		ht[rk[i]]=k;st[0][rk[i]]=k;
	}
	for(int i(1);i<=15;++i){
		for(int j(1);j+(1<<i-1)<=n;++j){
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
		}
	}
}

就是说我传入了一些数组进去,用函数求sa,我的写法只需要情况rk就够了,但交上去发现挂了,数据下载下来发现是多测不清空导致的,但一直看不出哪还需要清空,最后经过测试,把memset(rk,0,sizeof(rk));移到主函数就过了。然后又测试了一下,发现引用数组时memset在函数内会失灵或部分失灵。有没有大佬解答QAQ。

完整代码可以看我提交记录

2024/7/22 17:11
加载中...