后缀数组模板代码

代码来源：https://www.cnblogs.com/jinkun113/p/4743694.html

基数排序的总体逻辑：

（1）统计操作，统计每个元素个数，存入数组count

（2）求和操作，计算count前缀和；

（3）收集操作，将数组的所有元素收集，前缀和的下标即它的排名。

#include <bits/stdc++.h>
using namespace std;

// 可接收字符串的最大长度
#define MAXN 1005
// 字符种类数，英文单词则是26
#define MAXM 30

strar str[MAXN]; //字符串变量
int rank2start[MAXN];  //suffix array， rank2start[i]=j 表示所有后缀中排名为i的后缀在str中的起始位置为j
int arrayId[MAXN];  //arrayId[i]表示子串数组的编号,当子串长度为1时表示字符的编号
int start[MAXN]; //数组的起始位置
int c[MAXN];  //计数排序数组
int n; //当前字符串长度，也是后缀数组的个数
int m = MAXM; //str中不同后缀的种数

int main() {  
	// 输入一个字符串
	scanf("%s", str);
	n = strlen(str);
	
	// 1.统计每种字符的个数
    for (int i = 0; i < n; i++) {
		arrayId[i] = (str[i] - 'a' + 1); //将字符转换成下标
		c[arrayId[i]]++;
	}
	
	//2.求前缀和
    for (int i = 1; i < m; i++) {
		c[i] += c[i - 1];
	}
	//3.收集，得到每种字符（当前串长1）的排名
    for (int i = n - 1; i >= 0; i--) {
		//i表示str中第i个字符，其排名由c得出
		rank = c[arrayId[i]];
        rank2start[rank] = i;
		c[arrayId[i]] -= 1;//已经排好一个，待排序数减1
	}
	// 倍增的倍数（也是子串长度）k=1,2,4,8,16.....,当str中所有字符相同时，倍增达到上限n
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;//p表示字符串的排名
		
		// 长度不够k的后缀，没有第1关键字
        for (int i = n - k; i < n; i++) {//从后往前，子串长度递增
			start[p++] = i;
		}
        for (int i = 0; i < n; i++) {
			if (rank2start[i] >= k) {
				// t起始位置，后续必有rank2start[rank] = start[i]过程
				start[p++] = rank2start[i] - k;
			}
		}
		
        //排出每个后缀数组的名次
		memset(c, 0, sizeof(int) * m);
		//1.统计
        for (int i = 0; i < n; i++) {
			int array_id = arrayId[start[i]];//数组从t[i]开始，长度为k，给的编号为array_id
			c[array_id]++;
		}
		//2.求和
        for (int i = 0; i < m; i++) {
			c[i] += c[i - 1];
		}
		//3. 收集
        for (int i = n - 1; i >= 0; i--) {
			int array_id = arrayId[start[i]]
			int rank = c[array_id];
			rank2start[rank] = start[i];
			c[arrayId[start[i]]] -= 1;
		}
		
		//后续要用到array_id且要生成新的array_id，此处用start当旧arrayId用
        swap(arrayId, start);
        int p = 1;//子串的种类
		arrayId[rank2start[0]] = 0;
        for (int i = 1; i < n; i++) {
			int array1 = rank2start[i - 1];
			int array2 = rank2start[i];
			//倍增后新子串由array_id1_left和array_id1_right拼接而成,分别表示第2关键字和第1关键字
            // 此处注意rank2start[i - 1]和rank2start[i]所表示子串长度为k-1
			int array_id1_left = start[rank2start[i - 1]];
			int array_id1_right = start[rank2start[i - 1] + k];
			
			int array_id2_left = start[rank2start[i]];
			int array_id2_right = start[rank2start[i] + k];
			// 同一个子串，子串种类数不增加
			if (array_id1_left == array_id2_left && array_id1_right == array_id2_right) {
				arrayId[rank2start[i]] = p-1;
			} else {
				arrayId[rank2start[i]] = p++;
			}
		}
		//一个提前终止条件
        if (p >= n) break;
        m = p;
    }
    return 0;
}