suffix array – 后缀数组(倍增算法实现版)

使用倍增算法,反复调用基数排序,最后得到’名次数组rank’;
使用’名次数组rank’最终得到’后缀数组sa‘。

倍增算法的倍增体现在,每次处理的字符串长度增长方式为:2^0,2^1,2^2…(a^b表示a的b次方);
rank[i]表示首指针为i的序列,排名第几;
sa[i]表示排名第i的序列,首指针是多少;
注意编号开始的位置。

时间复杂度:
O(n*log[2](n))
log2n为倍增次数,n为基数排序的次数;

注意两个很重要的边界:一个是单个数据的范围,一个是数据个数的范围;
即,每个数据的最小值最大值,和一共要处理的数据的个数;

Counting sort – 计数排序

原理:

假设待排序对象为整数,且范围为1…1000;

举例:2,3,3,4

首先统计每个数字出现的次数,用c[i]表示。i表示数字,c[i]表示数字i出现的次数;

c[1] = 0;  c[2] = 1;  c[3] = 2;  c[4]=1;

然后从小到大,统计比每个数小的数一共有多少,用a[i]表示。i表示数字,a[i]=c[1]+c[2]+c[3]…+c[i]

a[2] = 1;a[3] = 3;a[4]=4;

接着算出每个数字的序数;遍历每个数字,算出其序数,将这个数字直接放在数组rank中,其对应的位置上;

for(int i = 1;i <= n;i ++) rank[– c[a[i]]] = a[i];

整个过程并没有一个数组专门来存所有待排列数字,只有一个数组rank来存储排列好的数字,所有一样大的数字之间的顺序取决于代码实现的过程。

《算法设计编程实验》中提到使用计数排序来实现后缀数组中rank数组的计算(这里的rank是后缀数组的rank),其实是笔误,那里用的是基数排序。