崔添翼 § 翼若垂天之云 › 构造Suffix Array的DC3算法
DC3算法的基本过程是这样的：首先构造出来一个superstring，这个串的每个字母都是原串的字母拼接上后面的两个字母，但这个串仅包含原串中下标模3不为0的位置。（递归地）求出这个串的SA，设为SA12。显然SA12中串的排列顺序与最终结果SA的排列顺序是相同的，只是SA12包含的串只有原串的2/3。
然后利用这个SA12和原串在线性时间内求出没有包含在SA12中的1/3的串的SA（也就是下标模3为0的那些串），设为SA0。求SA0的方法是：串的初始顺序是它们后面那个串在SA12中的顺序，然后再依据第一个字母进行一次RadixSort就可以了。也就是说SA0中的顺序可以仅用两个关键字来确定：第一关键字是第一个字母，第二关键字是后面的那个串在SA12中的位置。
Read full article from 崔添翼 § 翼若垂天之云 › 构造Suffix Array的DC3算法
No comments:
Post a Comment