后缀数组的定义及实现

《后缀数组的定义及实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、后缀数组的定义及实现1后缀数组的定义1.1后缀数组的相关概念(1)文本串的后缀：对于符号表Σ上的长度为n的文本串T[1...n]，文字串T的后缀是指从第i个字符开始到T的末尾所形成的子串T[i...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的一个字典序排序，即SA[i]=j表示后缀Tj是字符串集合{T0,T1,...Tn-1}中第i个最小字符串。排序后的后缀数组具有如下性质：

2、TSA[0]

3、本L。在1.1中提到：SA[i]=j表示后缀Tj是字符串集合{T0,T1,...Tn-1}中第i个最小字符串。因此SA[i]=j的两种表示理解方式：(1)表示Tj在字符串集合中排名(字典序排名)为i。(2)表示排名为i的后缀的Position。Rank数组：Rank数组是后缀数组的逆数组SA-1，即若SA[j]=i，则Rank[i]=j，其实质反映了T中的第i个后缀在所有后缀中的字典序排名为j。2倍增法后缀数组2.1倍增法后缀数组基本概念倍增法可以在logn步完成后缀数组的构造，n代表字符串A的长度。在倍增过程中，要维护两个整型、大小为N的数组Pos，Rank。Pos[i

4、]表示排名为i的后缀的Position，即在原字符串中的起始位置。Rank[i]表示在原字符串i处开始的后缀的排名，明显Pos[Rank[i]]=i。在第一阶段，所有后缀按首字母进行桶排序，即：所有首字母相同的后缀位于同一个桶内，且桶与桶之间按字典序排序。之后，每个阶段按照2倍于上次的字符数参与新一轮的桶排序。明显在k阶段，参与比较的字符数为2K个，用H表示，即所有前H个字符相同的后缀处于同一个桶内。现在假设H阶段已经排序完成，即Pos数组，Rank数组有正确的值，倍增算法的基本思路是：根据H阶段的Pos值，Rank值，构造2H阶段的Pos值，Rank值。假设Ai和Aj是

5、H阶段同一个桶内的两个后缀，这意味着：Ai和Aj的前H个字符是相同的，接下来需要比较后续的H个字符，即H+1到2H之间的字符。非常巧的是，这H个需要比较的字符也恰巧是后缀Ai+H，Aj+H的前H个字符，假设我们已经知道Ai+H，Aj+H按≤H的字典序关系（≤H的字典序表示后缀间按前H个字符的大小关系得到的字典序，后续的≤H，≤2H意义相同），则：从第一个桶的最左边（按≤H字典序最小）的后缀开始扫描，得到第一个后缀Ai，很明显Ai的前H个字符是最小的，考虑后缀Ai-H，其H到2H阶段的H个字符是最小的（Ai的前H个字符是最小的），所以Ai-H这个后缀应该处在它所在2H阶段的

6、相应桶内的最左端（最小）。所以，算法的整体思路就是：扫描H阶段按≤H有序的桶内的所有后缀，对于每一个后缀Ai，将Ai-H移动到它的桶内的下一个位置。当H阶段的扫描完成时，所有后缀都已经按≤2H的顺序处于对应的桶内，同一个桶内的所有后缀的前2H个字符都是相同的。在这个过程中，我们也需要维护一个BH数组，用来表示桶的边界，大小为n，初始值为全0，在每个桶的起始位置处为1，所以在BH数组中，假设两个连续的1对应的下标为S，V，则排名在[S,V−1]之间的所有后缀处在同一个桶内。伴随着H的增大，旧桶破裂，新桶产生，且桶的数目在增大（此过程对应BH数组的变化），在最后一个阶段，桶的

7、数目等于N，BH数组全为1，此时每个桶里只有一个后缀，排序完成。所以算法的大致流程为：1：所有后缀按首字母桶排序，得到对应的Pos，Rank，BH数组。2：在已有H阶段Pos，Rank，BH数据的情况下，按≤H的顺序扫描所有桶内的所有后缀Ai，移动Ai-H到对应位置（实质是修改Rank的值）。最终得到≤2H阶段的Pos，Rank，BH的值。3：若H>N,排序完成，此时Pos，Rank为最终值，BH全1。否则H=2H，转到2。按照上述算法，共需扫描log(n)次，每次都需要扫描所有的后缀，所以时间复杂度为O(nlogn)。在排序