Suffix Array

namespace suffixArray{
	const int MAXN = 2005; /// Length of string
	const int MAXL = 22;
	int n ,stp,mv,suffix[MAXN],tmp[MAXN];
	int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
	char str[MAXN];
	int LCP(int u,int v){
		int ret=0,i;
		for(i = stp; i >= 0; i--){
			if(rank[i][u]==rank[i][v]){
				ret += 1<<i;
				u += 1<<i;
				v += 1<<i;
			}
		}
		return ret;
	}
	bool equal(int u,int v){
		if(!stp)return str[u]==str[v];
		if(rank[stp-1][u]!=rank[stp-1][v]) return false;
		int a = u + mv < n ? rank[stp-1][u+mv] : -1;
		int b = v + mv < n ? rank[stp-1][v+mv] : -1;
		return a == b ;
	}
	void update(){
		int i;
		for(i = 0;i < n; i ++) sum[ i ] = 0;

		int rnk = 0;
		for(i = 0;i < n;i++){
			suffix[ i ] = tmp[ i ];
			if( i&&!equal(suffix[i],suffix[i-1])){
				rank[stp][suffix[i]]=++rnk;
				sum[rnk+1]=sum[rnk];
			}
			else rank[stp][suffix[i]]=rnk;
			sum[rnk+1]++;
		}
	}
	void Sort(){
		int i;
		for(i = 0; i < n; i ++ ) cnt[ i ] = 0;
		memset(tmp,-1,sizeof tmp);
		for(i = 0 ; i < mv; i ++){
			int idx = rank[ stp - 1 ][ n-i-1 ];
			int x = sum[ idx ];
			tmp[ x + cnt[ idx ] ] = n-i-1;
			cnt[ idx ]++;
		}
		for(i = 0;i < n; i ++ ){
			int idx = suffix[ i ] - mv;
			if(idx<0)continue;
			idx = rank[stp-1][idx];
			int x = sum[ idx ];
			tmp[ x + cnt[ idx ] ] = suffix[ i ] - mv;
			cnt[idx]++;
		}
		update();
		return;
	}
	bool cmp(const int &a,const int &b){
		if(str[a]!=str[b]) return str[a]<str[b];
		return false;
	}
	void input(){
		scanf("%s",str);
		n=strlen(str);
	}
	void init(){
		for(int i = 0;i < n;i++) tmp[ i ] = i ;
		sort(tmp,tmp+n,cmp);
		stp = 0;
		update();
		++stp;
		for( mv = 1; mv < n;  mv <<= 1){
			Sort();
			stp++;
		}
		stp--;
		for(int i = 0;i<=stp; i++)	rank[ i ][ n ] = -1;
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s