POJ 3693 后缀数组重复次数最多的连续重复子串倍增法以及D3法 - c++编程基础

void dc3(int *r,int *sa,int n,int m) // r为待匹配数组 n为总长度 m为字符范围
{
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i rn[F(wb[i])]=c0(r,wb[i-1],wb[i]) p-1:p++;
if(p else for(i=0;i for(i=0;i if(n%3==1) wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i for(i=0,j=0,p=0;i sa[p]=c12(wb[j]%3,r,wa[i],wb[j]) wa[i++]:wb[j++];
for(;i for(;j return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n) // 求height数组。
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i for(k k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
int RMQ[maxn];
int mm[maxn];
int best[20][maxn];//best[i][j] 表示从j开始的长度为2的i次方的一段元素的最小值
void initRMQ(int n)
{
int i,j,a,b;
for(mm[0]=-1,i=1;i<=n;i++)
mm[i]=((i&(i-1))==0) mm[i-1]+1:mm[i-1];
for(i=1;i<=n;i++) best[0][i]=i;
for(i=1;i<=mm[n];i++)
for(j=1;j<=n+1-(1< {
a=best[i-1][j];
b=best[i-1][j+(1<<(i-1))];
if(RMQ[a] else best[i][j]=b;
}
return;
}
int askRMQ(int a,int b)//询问a,b后缀的最长公共前缀
{
int t;
t=mm[b-a+1];b-=(1< a=best[t][a];b=best[t][b];
return RMQ[a] }
int lcp(int a,int b)
{
int t;
a=rank[a];b=rank[b];
if(a>b) {t=a;a=b;b=t;}
return(height[askRMQ(a+1,b)]);
}

char c;
int r[maxn*3],sa[maxn*3];
int ans[maxn];
char str[maxn*3];
int main()
{
int i,j,n,cas=0;

while(scanf("%s",str)!=EOF)
{
n=strlen(str);
if(n==1&&str[0]=='#') break;
for(i=0;i r[n]=0;
dc3(r,sa,n+1,30);//千万注意是n+1
calheight(r,sa,n);
for(i=1;i<=n;i++) RMQ[i]=height[i];
initRMQ(n);

/*
for(i=0; i printf("rank[%d] = %d\n",i,rank[i]);
printf("\n");
for(i=0; i printf("sa[%d] = %d\n",i,sa[i]);
*/
int l,mmax=-1,cnt,pos,t=0;
for(l=1;l {
for(i=0;i+l {
int k=lcp(i,i+l);
cnt=k/l+1;
pos=k%l;
pos=l-pos;
pos=i-pos;
if(pos>=0&&k%l!=0&&lcp(pos,pos+l)>=k) cnt++;////
if(cnt>mmax)
{
mmax=cnt;
t=0;
ans[t++]=l;
}
else if(cnt==mmax)
{
ans[t++]=l;
}
}

}
int flag=0,start;
for(i=1;i<=n;i++)
{
for(j=0;j {
l=ans[j];
if(lcp(sa[i],sa[i]+l)>=(mmax-1)*l)
{
start=sa[i];
l=l*mmax;
flag=1;
break;

}
}
if(flag) break;
}
printf("Case %d: ",++cas);
for (int i=0;i printf("\n");

}
return 0;
}

#include
#include
#define maxn 1000001

#define F(x) ((x)/3+((x)%3==1 0:tb))
#define G(x) ((x) int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+

POJ 3693 后缀数组 重复次数最多的连续重复子串 倍增法以及D3法 (三)

POJ 3693 后缀数组重复次数最多的连续重复子串倍增法以及D3法 (三)