namespace SuffixArray
{//SuffixArray
template <typename T> void exc(T &a, T &b) {T t=a; a=b; b=t;}
const int maxn = 100000*3;
int t1[maxn], t2[maxn];
void createSuffixArray(char Str[], int L, int SA[], int RK[])
{
	int *S1, *S2, *R, *B;
	S1 = SA, S2 = t1;
	R = RK, B = t2;
	int i, j, k, h;
	for (i=0; i<128; i++) B[i] = 0;
	for (i=0; i<L; i++) B[Str[i]]++;
	for (i=1; i<128; i++) B[i] += B[i-1];
	for (i=0; i<L; i++) S1[--B[Str[i]]] = i;
	for (R[S1[0]]=0, i=1; i<L; i++)
		if (Str[S1[i]] == Str[S1[i-1]]) R[S1[i]] = R[S1[i-1]];
		else R[S1[i]] = R[S1[i-1]]+1;

	for (h=1; h<L && R[S1[L-1]]<L-1; h<<=1)
	{
		for (i=0; i<L; i++) B[i] = 0;
		for (i=0; i<L; i++) B[R[i]]++;
		for (i=1; i<L; i++) B[i] += B[i-1];
		for (i=L-1; i>=0; i--) if (S1[i]>=h) S2[--B[R[S1[i]-h]]] = S1[i]-h;
		for (i=L-h; i<L-h/2; i++) S2[--B[R[i]]] = i;
		exc(S1, S2);
		
		for (B[S1[0]] = 0, i=1; i<L; i++)
			if (R[S1[i]]!=R[S1[i-1]] || R[S1[i]+h] != R[S1[i-1]+h])
				B[S1[i]] = B[S1[i-1]]+1;
			else 
				B[S1[i]] = B[S1[i-1]];
		exc(B, R);
	}
	if (R != RK) memcpy(RK, R, sizeof(int)*L);
	if (S1 != SA) memcpy(SA, S1, sizeof(int)*L);
}
void createHeight(char Str[], int L, const int SA[], const int RK[], int height[], int h[])
{
	int p = 0;
	for (int i=0; i<L; i++)
	{
		if (RK[i]==0) {h[i]=0; continue;}
		int j = SA[RK[i]-1];
		while (Str[i+p] == Str[j+p]) p++;
		h[i] = p;
		if (p>0) p--;
	}
	for (int i=0; i<L; i++) height[RK[i]] = h[i];
}

• Re:粘一个自己写的模版，不知道哪里错了，求各神牛帮忙看看！ (23) s030902202 2011-01-23 13:54:45