chyx's Blog

#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)

const int MAXN = 212345;
char str[MAXN];
int sa[MAXN], rank[MAXN], work[MAXN], bkt[MAXN], perm[MAXN], height[MAXN];
inline bool cmp(const int& a, const int& b, const int& l){
	return rank[a] == rank[b] && rank[a+l] == rank[b+l];
}
void build_sa(int n, int bkt_sz = 128){
	Rep(i,n)work[i] = str[i];

	// bucket sort [ work -> sa ]
	fill( bkt, bkt + bkt_sz, 0 );
	Rep(i,n) bkt[ work[i] ]++;
	partial_sum( bkt, bkt + bkt_sz, bkt );
	for(int i = n-1; i>=0; --i) sa[ --bkt[work[i]] ] = i;
	// current rank
	copy( work, work + n, rank );

	for(int step = 1; ; step *= 2){
		int p = 0; for(int i = n-step; i < n; ++i) perm[p++] = i;
		Rep(i,n)if(sa[i] >= step) perm[p++] = sa[i] - step;
		assert( p == n );
		Rep(i,n)work[i] = rank[ perm[i] ];

		// bucket sort [ work -> sa ]
		fill( bkt, bkt + bkt_sz, 0 );
		Rep(i,n) bkt[ work[i] ]++;
		partial_sum( bkt, bkt + bkt_sz, bkt );
		for(int i = n-1; i>=0; --i) sa[ --bkt[work[i]] ] = perm[i]; // 这句和前面不一样

		bkt_sz = 0;
		work[sa[0]] = bkt_sz++;
		for(int i = 1; i < n; ++i) work[sa[i]] = cmp(sa[i], sa[i-1], step ) ? bkt_sz-1 : bkt_sz++;
		copy( work, work + n, rank );
		if( bkt_sz == n ) break;
	}

	int cur = 0;
	for(int i = 0; i < n-1; ++i){
		if( --cur < 0 ) cur = 0;
		while( str[i + cur] == str[ sa[rank[i]-1] + cur ] ) cur++;
		height[rank[i]] = cur;
	}
}