Suffix Array and Longest Common Prefix

Suffix Array and Longest Common Prefix implementation with Stable Radix Sort

#include <cstdio>

const int MAXN = 128;

int D[MAXN + 1];
void radixSort(const int *A, const int *B, int *C, int N, int M) {
	int i;
	for (i = 0; i <= M; i++) D[i] = 0;
	for (i = 0; i < N; i++) D[B[A[i]]]++;
	for (i = 1; i <= M; i++) D[i] += D[i - 1];
	for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}

int B[MAXN + 1];
int T[MAXN];
void suffixArray(const char *A, int *C, int N) {
	int i, j, k, l;
	for (i = 0; i < N; i++) {
		B[i] = A[i];
		T[i] = i;
	}
	radixSort(T, B, C, N, 128);
	for (i = k = 1; i < N && k < N; i <<= 1) {
		for (k = 0; k < i; k++) T[k] = k - i + N;
		for (j = 0; j < N; j++) if (C[j] >= i) T[k++] = C[j] - i;
		radixSort(T, B, C, N, N);
		T[C[0]] = k = 1;
		for (j = 1; j < N; j++) {
			if (B[C[j]] != B[C[j - 1]] || B[C[j] + i] != B[C[j - 1] + i]) k++;
			T[C[j]] = k;
		}
		for (j = 0; j < N; j++) B[j] = T[j];
	}
}

void LCP(const int *A, const char *B, int *C, int N) {
	int i, j;
	for (i = 0; i < N; i++) T[A[i]] = i;
	for (i = j = 0; i < N; i++) {
		if (T[i]) {
			while (B[i + j] == B[A[T[i] - 1] + j]) j++;
			C[T[i]] = j;
		}
		if (j) j--;
	}
}

char S[12] = "abracadabra";
int R[11], Q[11];

int main() {
	int i;
	suffixArray(S, R, 11);
	LCP(R, S, Q, 11);
	for (i = 0; i < 11; i++) printf("%d %d %d\n", i, R[i], Q[i]);
}