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为基数排序的次数;

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

Leave a Reply

Your email address will not be published. Required fields are marked *