1） 计算名次数组Rank与后缀数组SA
采用倍增算法，先求出名次Rank，然后在O(n)时间内求得后缀数组SA。用倍增的方法对每个字符开始的长度为2^k 的子字符串进行排序，求出排名，即rank 值。k 从0 开始，每次加1，当2k 大于n 以后，每个字符开始的长度为2^k 的子字符串便相当于所有的后缀。并且这些子字符串都一定已经比较出大小，即rank 值中没有相同的值，那么此时的rank 值就是最后的结果。每一次排序都利用上次长度为2^(k-1) 的字符串的rank 值，那么长度为2^k 的字符串就可以用两个长度为2^(k-1) 的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为2k 的字符串的rank 值。以字符串"aabaaaab"为例，整个过程如下图所示。其中x、y 是表示长度为2k 的字符串的两个关键字。
Read full article from 数据结构之后缀数组 | 董的博客
No comments:
Post a Comment