学步园

这个星期写了后缀数组，具体是参考

http://wenku.baidu.com/link?url=9yE_Qn-Toh9IvB4fR7OqU8xJ3WSXsKX6RO4BDJeOxnENE4AT3Jx0uQqoSyNrF8gZTI9fcfiMNksmX3LCFt1FLK0ogZnQ2XNhjbGtxNzOmRW

的

后缀排序

void suffix_sort(){
	static int wx[maxn],wy[maxn],wv[maxn],ws[maxn];
	m='z'+1; ++n; int i,*x=wx,*y=wy;
	for (i=0;i<n;++i) ++ws[x[i]=s[i]];
	for (i=1;i<m;++i) ws[i]+=ws[i-1];
	for (i=n-1;i>=0;--i) sa[--ws[x[i]]]=i;
	for (int len=1,p=0;p<n;len<<=1,m=p){
		for (p=0,i=n-len;i<n;++i) y[p++]=i;
		for (i=0;i<n;++i) if (sa[i]>=len) y[p++]=sa[i]-len;
		for (i=0;i<m;++i) ws[i]=0;
		for (i=0;i<n;++i) ++ws[wv[i]=x[y[i]]];
		for (i=1;i<m;++i) ws[i]+=ws[i-1];
		for (i=n-1;i>=0;--i) sa[--ws[wv[i]]]=y[i];  // x is rank
		for (swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;++i)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],len)?p-1:p++;   // y is rank 
	}
	for (int i=0;i<n;++i) rank[i]=x[i];
}

求height

void get_height(){
	int len=0;
	for (int i=0;i<n-1;height[rank[i++]]=len)
		for (len?--len:0,j=sa[rank[i]-1];s[i+len]==s[j+len];++len);
}

刷过的一些题，就是论文上的那些题，还有一些水题