对S12进行排序, S12中的每个值n都代表一个三元组
(buf[n],buf[n+1],buf[n+2]),排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n %...n1为i%3==1的个数。
3. 如果任意两个三元组都不相等,说明仅凭前三个字母就可以对后缀确定顺序,则直接执行步骤4。否则,对s12中的数据递归执行DC3。
4....根据s12来生成数组SA12,然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序,与SA12进行有序合并,成为SA。SA即为后缀数组的有序列表。...从上面列表可以看出’1,2,3’ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序(不满足步骤3),因为要接着递归执行,先得到SA’如下
[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10...在步骤4进行有序合并时,i%3==1时,会将3元组扩展成4元组,i%3==2时,将3元组扩展成5元组,之后再比较。