学步园

#define SIZE 200005 
char S[SIZE];
int N,sa[SIZE], height[SIZE], rank[SIZE], tmp[SIZE], top[SIZE]; 
int rmq[SIZE][20]; 
//S[] 字符串
//N 字符串长度
//rank[i] i是第几名 
//sa[i] 第i名是什么
//height[i] 第i名和第i-1名的最长公共前缀长度
//名次：1~N序号：0~N-1
void makesa(){ // O(SIZE * log SIZE)
	int i, j, n, len, na;
	n=N+1;
	S[n-1]=0;
	na = (n < 256 ? 256 : n);
	memset(top, 0, na * sizeof(int));
	//-------char------
	for (i = 0; i < n ; i++) top[ rank[i] = S[i] & 0xff ]++;
	for (i = 1; i < na; i++) top[i] += top[i - 1];
	for (i = 0; i < n ; i++) sa[ --top[ rank[i] ] ] = i;
	//---------char----*/
	/*-------int-------
	for(i=0;i<n;i++){
		sunit[i].id=i;
		sunit[i].v=S[i];
	}
	sort(sunit,sunit+n);
	int t=0;
	for(i=0;i<n;i++){
		sa[i]=sunit[i].id;
		if(i&&sunit[i].v!=sunit[i-1].v){
			t++;top[t+1]+=top[t];
		}
		rank[sunit[i].id]=t;top[t+1]++;
	}
	for(t++;t<n;t++)top[t]=top[t-1];
	//-----------------*/
	for (len = 1; len < n; len <<= 1) {
		for (i = 0; i < n; i++) {
			j = sa[i] - len; if (j < 0) j += n;
			tmp[ top[ rank[j] ]++ ] = j;
		}
		sa[ tmp[ top[0] = 0 ] ] = j = 0;
		for (i = 1; i < n; i++) {
			if (rank[ tmp[i] ] != rank[ tmp[i-1] ] ||
			rank[ tmp[i]+len ]!=rank[ tmp[i-1]+len ])
			top[++j] = i;
			sa[ tmp[i] ] = j;
		}
		memcpy(rank, sa , n * sizeof(int));
		memcpy(sa , tmp, n * sizeof(int));
		if (j >= n - 1) break;
	}
}
void lcp(){ // O(4 * SIZE)
	int i, j, k,n=N+1;
	for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++)
		while (k >= 0 && S[i] != S[ sa[j-1] + k ])
		height[j] = (k--), j = rank[ sa[j] + 1 ];
}  
void get_rmq(int x[],int s,int e){  
	int i,j,l,len=e-s+1;  
	for(i=s;i<=e;i++)rmq[i][0]=x[i];  
	for(j=1,l=2;l<=len;j++,l<<=1){  
    	for(i=s;i+l-1<=e;i++)rmq[i][j]=f_min(rmq[i][j-1],rmq[i+l/2][j-1]);  
	}  
}  
int query_min(int s,int e){
	if(s>e)return 0;
	int j=log(e-s+1.)/log(2.),l=1<<j;
	return f_min(rmq[s][j],rmq[e-l+1][j]);
}