后缀数组

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define LETTERS 30
#define MAX_ARRAY_SIZE 200005 
int gStrLen;
int gStr[MAX_ARRAY_SIZE];			//将字符串转换为整数数组，且在末尾加一个最小的之前未出现的数字


int gCount[MAX_ARRAY_SIZE];			//用于计数排序和基数排序
int gRank[MAX_ARRAY_SIZE];			//将序列中每个元素都给一个rank，用于排序
int gSuffixArray[MAX_ARRAY_SIZE];	//后缀数组
int gOrderBySecondKey[MAX_ARRAY_SIZE];//倍增算法基数排序时，将gRank按照第二关键字排序后的顺序
int gFirstKeyArray[MAX_ARRAY_SIZE]; //将gRank按照gOrderBySecondKey排列的结果，用于对第一关键字进行排序 
//gFirstKeyArray[i] = gRank[gOrderBySecondKey[i]]
int gHeight[MAX_ARRAY_SIZE];


//比较两个元素是否相等，分别比较第一关键字和第二关键字
bool Compare(int* arr, int a, int b, int step){
	return arr[a] == arr[b] && arr[a + step] == arr[b + step];
}

//将字符串转换为初始整数数组
void GetStr(char* str){
	memset(gStr, 0, sizeof(gStr));
	gStrLen = strlen(str);
	for (int i = 0; i < gStrLen; i++){
		gStr[i] = str[i] - 'a' + 1;
	}
	gStr[gStrLen] = 0;
	gStrLen++;
}

//求后缀数组
void GetSuffixArray(){
	int n = gStrLen;

	//求step = 0的后缀数组
	memset(gCount, 0, sizeof(gCount));
	for (int i = 0; i < n; i++){
		gRank[i] = gStr[i];//根据字符串的内容，将gRank初始化，gRank[i]相当于位置i处的元素值
		gCount[gRank[i]] ++; 
	}
	int m = LETTERS;
	for (int i = 1; i < m; i++){
		gCount[i] += gCount[i - 1];
	}
	for (int i = n - 1; i >= 0; i--){
		gSuffixArray[--gCount[gRank[i]]] = i;  //step = 0的后缀数组
	}

	int step = 1;
	int *rank = gRank, *order_by_second_key = gOrderBySecondKey;
	while (step < n){  //倍增算法
		int p = 0;
		//根据上次求得的 gSuffixArray 求gRank按照第二关键字排序后的位置，
		//gOrderBySecondKey[i] 存放的是gRank按照第二关键字排序，第i大的位于 gRank数组的位置（用作后续的第一关键字的位置）
		for (int i = n - step; i < n; i++){ 
			order_by_second_key[p++] = i;   //i >n-step时，第二关键字的位置 > n-1，因此直接视为0，放到gOrderBySecondKey最开始的位置
		}
		for (int i = 0; i < n; i++){//上次的gSuffixArray[i]，如果位于 [step, n-1]区间内，则可以直接得到其 第一关键字的位置
									//且按照 i从小到大的顺序，可以保证基数排序的正确性
			if (gSuffixArray[i] >= step){
				order_by_second_key[p++] = gSuffixArray[i] - step;
			}
		}
		for (int i = 0; i < n; i++){ //按照第二关键字大小得到的第一关键字的序列
			gFirstKeyArray[i] = rank[order_by_second_key[i]];
		}

		//基数排序
		for (int i = 0; i < m; i++){
			gCount[i] = 0;
		}
		for (int i = 0; i < n; i++){
			gCount[gFirstKeyArray[i]] ++;
		}
		for (int i = 1; i < m; i++){
			gCount[i] += gCount[i - 1];
		}
		for (int i = n - 1; i >= 0; i--){
			gSuffixArray[--gCount[gFirstKeyArray[i]]] = order_by_second_key[i];
		}

		//此时，更新 rank的值（需要根据第二关键字和第一关键字）
		int* tmp = rank; rank = order_by_second_key; order_by_second_key = tmp;
		rank[gSuffixArray[0]] = p = 0;
		for (int i = 1; i < n; i++){ //已知 新的step下的子串的次序，直接比较相邻的rank即可
			if (Compare(order_by_second_key, gSuffixArray[i], gSuffixArray[i - 1], step)){
				rank[gSuffixArray[i]] = p;
			}
			else{
				rank[gSuffixArray[i]] = ++p;
			}
		}
		m = p + 1;
		step *= 2;
	}
}
//求height数组
void GetHeight(){
	int n = gStrLen;
	for (int i = 0; i < n; i++){
		gRank[gSuffixArray[i]] = i; //由于在构造str数组的时候，手动添加了0在最末尾，使得gSuffixArray[0]肯定为n
	}
	int k = 0, j;
	for (int i = 0; i < n; i++){
		if (k){
			k--;
		}
		j = gSuffixArray[gRank[i] - 1];
		while (j + k < n && i + k < n&& gStr[i + k] == gStr[j + k]){
			k++;
		}
		gHeight[gRank[i]] = k;  // 计算得到 h[i]
	}
}

//for debug
/*
void printstr(int n){
	printf("string = 
");
	for (int i = 0; i < n; i++){
		printf("%d ", gStr[i]);
	}
	printf("
");
}
void printsuffix(int n){
	printf("suffix = 
");
	for (int i = 0; i < n; i++){
		printf("%d ", gSuffixArray[i]);
	}
	printf("
");
}
void printheight(int n){
	printf("height = 
");
	for (int i = 0; i < n; i++){
		printf("%d ", gHeight[i]);
	}
	printf("
");
}
void printSuffix(char* str, int n){
	for (int i = 0; i < n; i++){
		printf("%d ", gSuffixArray[i]);
		printf("%s
", str + gSuffixArray[i]);
	}
}
void printrank(int n){
	printf("rank = 
");
	for (int i = 0; i < n; i++){
		printf("%d ", gRank[i]);
	}
	printf("
");
}
*/