后缀数组的定义及实现.doc

后缀数组的定义及实现1 后缀数组的定义1.1 后缀数组的相关概念(1) 文本串的后缀：对于符号表上的长度为n的文本串T1.n，文字串T的后缀是指从第i个字符开始到T的末尾所形成的子串Ti.n，1 i n。(2) 子串：在长度为 n的文字串T中，下标从i到j的连续的(j-i+1)个字符所组成的字符序列就是文字串T的一个长度为( j i + 1)子串，其中1 i j n。(3) 后缀数组：后缀数组SA是T的所有后缀T0, T1, . Tn-1的一个字典序排序，即SAi = j表示后缀Tj是字符串集合T0, T1, . Tn-1中第i个最小字符串。排序后的后缀数组具有如下性质：TSA0 TSA1 N,排序完成，此时Pos，Rank为最终值，BH全1。否则H=2H，转到2。按照上述算法，共需扫描log(n)次，每次都需要扫描所有的后缀，所以时间复杂度为O(n log n)。在排序过程中，需要维护Pos，Rank，BH等辅助空间，其大小都为n，所以空间复杂度为O(n)。2.2 算法Algorithm 1: Suffix Sorting(A, Pos, n)Input: A, nOutput: PosVariables: Rankn, Countn; BHn+1, B2Hn+1/*Assume that you have the right value of Pos、Rank、BH using a radix sorting with compareing the first singal-symbol of all the suffixs, our main point is to explain how compute Pos ,Rank and BH of stage 2H while using the information of stage H */ 1: for H 1, 2, 4, 8, ., n1 do 2: for each H_BucketL, R do 3: CountL 0 4: for c L to R do 5: RankPosc L 7: d NH 8: e Rankd 9: Rankd e + Counte10: Counte Counte + 111: B2HRankd 112:for each H_bucketL,R in order H_order do13: for c L to R do14: d PoscH15: if d 0 then16: Rankd Rankd+CountRankd17: CountRankd CountRankd + 118: B2HRankd 119: for c L to R do20: d Posc H21: if d 0 then22: if B2HRankd then23:e min(j : j Rankd and (BHj or not B2Hj)24:for f Rankd + 1 to e 1 do25:B2Hf 026: for i 0 to N1 do27: PosRanki i28: for i 0 to N1 do29:if B2Hi and not BHi then30:BHi B2Hi输入参数A表示原文本字符串，n表示原本字符串的长度，Pos数组为最终的返回值。算法第2行表示取每个通的左右边界，第12行意思类似，只是按照桶的H字典序进行，即先取“小”桶的边界，再取“大”桶的边界。本算法主要突出由H阶段的Pos值构造2H阶段的Pos值的核心过程。算法中用到了三个大小为n的整型数组，Pos、Rank和Count和两个大小为n+1的Boolean型数组BH和B2H。Posi表示名次为i的后缀在原字串中的起始位置，Rank数组是Pos数组的逆，即RankPosi=i，Rankj表示从j处开始的后缀的排名。Count数组是个临时数组，用来保存在扫描过程中，某个桶内已经移动的后缀的个数。在该桶内的后缀都未移动时，所有后缀的排名与最左端后缀的排名相同，则该桶内第CountRankd个移动的后缀的排名更新为Rankd+CountRankd1，这是算法的核心。BH数组用来