看以下代码:
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。
完整代码可以看我提交记录