[ Suffix Array DC3 algoruthm ] 後綴數組線性DC3演算法

這邊提供後綴數組DC3算法的模板，他是一個能在線性時間$\ord N$內求得後綴數組的演算法，注意這邊傳入的陣列s及sa長度必須是字串長的3倍以上，因為DC3會用到大量的記憶體，而且會利用傳入的陣列s的空間進行計算，因此傳入的陣列s必須是int範圍，而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過，因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2

因為是遞迴的關係，所以常數很大，但在大數據的時候比倍增法快
關於DC3演算法的介紹請看這兩篇文章:
http://ching.im/post/algorithm/difference-cover-modulo-algorithm
《后缀数组——处理字符串的有力工具》

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

在傳入的參數中最後一個A為最大的字元+1通常設為'z'+1

以下提供模板(其實code挺短的):

	#define F(x) (x)/3+((x)%3==1?0:tb)
	#define G(x) (x)<tb?(x)*3+1:((x)-tb)*3+2
	int wa[3*maxn+5],wb[3*maxn+5],wv[3*maxn+5],c[maxn+5];
	inline bool c0(int *s,int a,int b){
	return s[a]==s[b]&&s[a+1]==s[b+1]&&s[a+2]==s[b+2];
	}
	inline bool c12(int k,int *s,int a,int b){
	if(k==2)return s[a]<s[b]||s[a]==s[b]&&c12(1,s,a+1,b+1);
	else return s[a]<s[b]||s[a]==s[b]&&wv[a+1]<wv[b+1];
	}
	inline void radix_sort(int *s,int *a,int *b,int len,int A){
	static int i;
	for(i=0;i<len;++i)wv[i]=s[a[i]];
	for(i=0;i<A;++i)c[i]=0;
	for(i=0;i<len;++i)++c[wv[i]];
	for(i=1;i<A;++i)c[i]+=c[i-1];
	for(i=len-1;i>=0;--i)b[--c[wv[i]]]=a[i];
	}
	void dc3(int *s,int *sa,int len,int A){
	int i,j,*san=sa+len,ta=0,tb=(len+1)/3,tbc=0,p;
	int *rn=s+len;
	s[len]=s[len+1]=0;
	for(i=0;i<len;++i){
	if(i%3!=0)wa[tbc++]=i;
	}
	radix_sort(s+2,wa,wb,tbc,A);
	radix_sort(s+1,wb,wa,tbc,A);
	radix_sort(s,wa,wb,tbc,A);
	for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;++i){
	rn[F(wb[i])]=c0(s,wb[i-1],wb[i])?p-1:p++;
	}
	if(p<tbc)dc3(rn,san,tbc,p);
	else for(i=0;i<tbc;i++)san[rn[i]]=i;
	for(i=0;i<tbc;++i){
	if(san[i]<tb)wb[ta++]=san[i]*3;
	}
	if(len%3==1)wb[ta++]=len-1;
	radix_sort(s,wb,wa,ta,A);
	for(i=0;i<tbc;++i)wv[wb[i]=G(san[i])]=i;
	for(i=0,j=0,p=0;i<ta&&j<tbc;++p){
	sa[p]=c12(wb[j]%3,s,wa[i],wb[j])?wa[i++]:wb[j++];
	}
	for(;i<ta;++p)sa[p]=wa[i++];
	for(;j<tbc;++p)sa[p]=wb[j++];
	}
	#undef F
	#undef G
	/*
	DC3的輸入陣列s必須能儲存0~len的數值，所以設為int
	s及sa陣列的大小必須大於3*maxn
	*/

view raw DC3.cpp hosted with ❤ by GitHub