后缀数组

后缀数组是处理字符串的一种常用算法，是后缀树的一种精巧的替代品，它比后缀树更容易编程实现，且效率和后缀树相当。

后缀数组定义

子串: 字符串S的子串r[i, j]（i <= j），表示r串中从i到j这一段形成的字符串。
后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为 Suffix(i), Suffix(i) = r[i, len-1]。一个串S长度为len(S)，则它有len(S)个后缀 Suffix(0), Suffix(1).... Suffix(len(S) - 1)
后缀数组：SA是一个一维数组，它表示将字符串S的len(S)个后缀进行排序（一般字典序）之后第i个顺序的Suffix(k)表示的后缀在S中的起始位置。
    比如:"abcad"的后缀分别为 Suffix[0] = "abcad", Suffix1 = "bcad", Suffix2 = "cad", Suffix3 = "ad", Suffix4 = "d"，对这些后缀进行排序之后，可以得到{"abcad", "ad", "bcad", "cad", "d"}。对应的Suffix的顺序（即Suffix在S中的起始位置）是{0, 3, 1, 2, 4} = SA.
名次数组： Rank[i]保存S的后缀Suffix[i]在排序之后位于第几位。仍然使用上面的例子，可以得到Rank = {0, 2, 3, 1, 4}
    简单的说，后缀数组SA表示“排第几的是谁？”，而名次数组Rank表示“你排第几？”。可以看出SA数组和Rank数组互为逆运算。即 Rank[SA[i]] = i, SA[Rank[i]] = i.

    如上图所示，为一个后缀数组和名次数组示例。其中下标从1开始。

设字符串的长度为n。为了方便比较大小，可以在字符串的后面添加一个字符，这个字符在前面的字符中没有出现过，且比前面的字符都要小。在求出Rank数组之后，可以用O(1)的时间比较任意两个后缀的大小，在求出后缀数组或名次数组中的人任意一个之后，都可以用O(n)的时间求出另一个。

后缀数组的求法——倍增算法

算法思想
    算法主要思想是通过倍增的方法对每个字符开始的长度为2^k的字符串进行排序，求出排名。k从0开始，每次增加1，直到2^k大于等于n以后，每个字符开始的长度为2^k的子字符串便相当于所有的后缀。并且这些字符串都一定已经比较出大小，即rank值中没有相同的值，那么此时的rank就是最后的结果。
算法步骤
    每一次排序都利用上次长度为2^(k-1)的字符串的rank值，长度为2^k的字符串可以视为两个长度为2^(k-1)的字符串的拼接，两个长度为2^(k-1)的串的rank已经求出，记为rank1、rank2，则在计算长度为2^k的字符串的rank时，通过基数排序比较(rank1, rank2）的二维数即可（先比较rank1，rank1相同再比较rank2）。

    如上图所示，先对每个位置开始的长度为1的子串进行比较，得到rank；然后长度为2，此时将两个长度为1的子串合并看成一个串，其rank进行高低位合并，进行比较；之后类似。
复杂度分析
    共需要进行

后缀数组的求法——DC3算法

算法思想
    将后缀分为两类：一类是起始位置为3的倍数的Suffix(i){i % 3 == 0}，一类是起始位置不是3的倍数的Suffix(i）{i % 3 != 0}.
    然后将起始位置不是3的倍数的后缀 Suffix(1)和Suffix(2)进行拼接扩充，得到然后每3个字符合并为1个，成为长度为2n/3的新串。容易发现，新串的Rank数组求出之后，可以直接求出原串中起始位置不是3的倍数的Suffix(i)。这样，可以对子问题（求长度为2n/3的新串的Rank）进行递归求解；
    求出起始位置不是3的倍数的后缀的rank之后，可以很容易的求出起始位置为3的倍数的后缀的rank，类似倍增算法进行两个关键字基数排序即可。

算法步骤
（1）先将后缀分为两部分，然后对第一部分的后缀排序
将后缀分为两部分，第一部分是后缀k（k%3==0)，第二部分是后缀k(k%3 !=0)。先对所有起始位置不是3的倍数的后缀进行排序，即Suffix(1), Suffix(2),Suffix(4）,Suffix(5)... 做法是：
将Suffix(1)和Suffix(2)进行连接，如果这两个后缀的长度不是3的倍数，则先各自在末尾加0使得长度都变为3的倍数。然后每3个字符为一组，进行基数排序，将每组字符“合并”成一个新的字符（此时新的字符串中字符数约为 2n/3），然后递归求这个新串的后缀数组。在得到新串的SA之后，就可以得到原串中起始位置不是3的倍数的SA。

（2）利用（1）的结果，对第二部分的后缀排序
第二部分的后缀为起始位置为3的倍数的后缀，可以看成是一个字符加上一个起始位置为3k+1的后缀，起始位置为3k+1的后缀的rank已经求出，因此只需要一次基数排序即可求出剩下的后缀的SA。

(3) 将（1）和（2）的结果进行合并
该合并操作和归并排序的合并操作类似，每次需要比较两个后缀的大小。分两种情况考虑：
情形一是Suffix(3*i)和Suffix(3*j+1)的比较

Suffix(3*i) = r[3*i] + Suffix(3*i+1)
Suffix(3*j+1) = r[3*j+1] + Suffix(3*j+2)

其中，Suffix(3*i+1)和Suffix(3*j+2)的比较结果可以通过步骤（2）的结果快速得到。
情形二是Suffix(3*i)和Suffix(3*j+2)的比较

Suffix(3*i) = r[3*i] + r[3*i+1] + Suffix(3*i+2)
Suffix(3*j+2) = r[3*j+2] + r[3*j+3] + Suffix(3*(j+1)+1)

其中，Suffix(3*i+2)和Suffix(3*(j+1)+1)的比较结果可以通过步骤（2）的结果快速得到。

复杂度分析
步骤（1）的排序时间为O(n),新的字符串的长度不超过2n/3，求新串的SA的时间为f(2n/3), 步骤（2）和步骤（3）的时间为O(n).因此 f(n) = f(2n/3) + O(n).可以得到 f(n) = O(n).

后缀树组的height数组

后缀数组解决字符串问题的时候，经常用到后缀数组的一个附属——height数组。height数组定义为：

height[i]表示后缀 Suffix(SA(i))和Suffix(SA(i-1))的最长公共前缀长度。即第i大的后缀和第i-1大的后缀的最长公共前缀长度。

性质1
对于任意的j和k，假设 rank[j] < rank[k]，有Suffix(j)和Suffix(k)的最长公共前缀的长度为 height[rank[j]+1], height[rank[j]+2], height[rank[j]+3]....height[rank[k]]的最小值。
这是因为，Suffix(j)表示从位置j处开始的后缀，Suffix(k)表示从位置k处开始的后缀，rank[j] < rank[k].将第rank[j]大到第rank[k]大的后缀按顺序依次排列起来，两两比较，用反证法可以证明第i大和第i+2大的后缀的公共前缀长度为第i大与第i+1大的后缀的公共前缀长度height(i+1)和第i+1大与第i+2大的后缀的公共前缀的长度height(i+2)的最小值。
例如字符串"aabaaaab"，求后缀"abaaaab"和"aaab"的最长公共前缀。

性质2
定义h数组，h[i] = height[rank[i]]，即Suffix(i)和它的前一名后缀的最长公共前缀长度。h[i] >= h[i-1]-1
设Suffix(k)是排在Suffix(i-1)前一名的后缀，他们的最长公共前缀是h[i-1]。那么Suffix(k+1)将排在Suffix(i)的前面（这里要求h[i-1] > 1，若h[i-1] <=1, 原式显然成立），并且Suffix(k+1)和Suffix(i)的最长公共前缀是h[i-1]-1（相比Suffix(k)和Suffix(i-1)分别去掉首字符）。所以Suffix(i)和它的前一名后缀的最长公共前缀至少是h[i-1]-1.

实现(c++)

倍增算法
需要注意，基数排序时候，按照先排低位后排高位的顺序，多次使用计数排序。

#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("
");
}
*/