——《高级数据结构》
“linear work suffix array construction”的文章中提出了后缀数组的线性时间构造算法。其中DC3算法的时间复杂度和空间复杂度均为O(n)；其中DC3（Difference Covor modulo3）算法的时
间复杂度仍为O(n)；更是一般化的DC算法具有O（vn）的时间复杂度和O(nv的1/2)的空间复杂度。本节介绍DC3算法并给出实现的代码，之后将介绍更一般形式的DC算法。

果i mod 3<>0，那么取出该后缀，这个过程称作“采样”。我们首先对所有被采样的后缀构建后缀数组，这个递归过程将原问题的规模缩减为2/3.
2.对于剩下的那些未被采样的后缀，利用第1步的结果构造后缀数组。
3.将上述两个步骤得到的后缀数组进行合并。
接下来我们具体地看DC3算法的执行步骤。即字符串T=“yabbadabbado$”。

步骤一 采样
对于k属于[0,2],我们定义集合Bk={i|i属于[0,n]且i mod 3=k}。集合C=U1并U2，称为“采样集合”。回顾后缀集合的定义，Suffix(C)就称为后缀采样集合。
对于我们使用的例子而言，B1={1,4,7,10}，B2={2,5,8,11}。从而可以得到C={1,4,7,10,2,5,8,11}。
步骤二 构建后缀采样集合的后缀树组
首先，我们通过对原串构建两个新的字符R1和R2.对于k=1,2，Rk为从原串第k个字符开始，每三个一组得到的新字符串，即Rk={tktk+1tk+2}[tk+3tk+4tk+5]...直到T的末尾。如果
末尾不够补全三元组的话，用结束符$填充。注意，现在我们的“字符”概念就是每一个三元组。接着，我们将R2接在R1的后面，得到字符串R。可以看到，从R的每个“字符”开始的后缀就是
被采样的那些后缀（如果碰到结束符$就停止的话）。所以，接下来的过程就是构造R的后缀数组。上述例子中，R=[aab][ada][bba][do$][bba][dab][bad][o$$].
  接着，我们对R使用基数排序，得到每个“字符”的名次，相当于对“字符”结集进行离散化。如果R中任意两个“字符”都不相同，那么显然，我们已经得到了R的后缀数组--------此时后缀的排名
  等价于每个后缀第一个"字符"的排名，如果不满足这个条件，那么只需要递归执行即可——对字符串R调用DC3算法得到它的后缀数组。以下是上述字符串R的名次数组对应和后缀数组：
   Rank‘=(0,1,4,6,3,5,2,7) 
   SA'=(0,1,6,4,2,5,3,7)
   这样，我们可以获得 被采样的这些后缀之间相对的排名。把它们计入Rank数组中（没有采样的那些后缀的名次不计算）。我们把$也计入进来，同时为了描述方便，我们再给T补充两个结束符$。

步骤三 计算未被采样的后缀名次数组
对于那些没有被采样的后缀Suffix(i)属于Suffix(B0),我们用二元组（ti，Rank(Suffix(i+1))）来表示。由于对字符串T补充了两个$，并且（i+1）mod 3<>0，所以Rank(Suffix(i+1))肯定已经被计算了。因此，对于后缀集合Suffix(B0)中任意两个后缀Suffix(i)和Suffix(j)，它们的字典序关系就是二元组(ti,Rank(Suffix(i+1))) 和(tj,Rank（Suffix(j+1)）)的序关系。（ti,Rank(Suffix(i+1))）<(tj,Rank(Suffix(j+1)))等价于ti<tj或者ti=tj且Rank(Suffix(i+1))<Rank(Suffix(j+1)).
有了上述的二元组比较方法，我们便可以应用基数排序对后缀集合Suffix(B0)进行排序计算其名次数组了。注意，步骤二和步骤三之间的名次数组没有交集，因而不可以进行直接比较，我们需要执行步骤四来合并这两个结果。

步骤四：合并两个名次数组
（1）两个后缀集合各自维护一个指针指向当前集合中字典序最小的后缀
（2）比较两个指针指向的后缀，将字典序较小的后缀添加进最后的结果中并赋予相应的名次，同时从原集合中删去这个后缀。
（3）如果有一个集合为空，那么将另一个集合所有后缀依次添加进最后的结果，算法结束；否则，继续执行（2）。
关键的步骤为比较两个后缀。假设后缀Suffix(i)属于Suffix©,Suffix(j)属于Suffix(B0),我们分两种情况比较它们的大小关系。
（1)如果i属于B1，那么：
Suffix(i)<Suffix(j)等价于（ti,Rank(Suffix(i+1))）<(tj,Rank(j+1));
(2)如果i属于B2，那么
Suffix(i)<Suffix(j)等价于(ti,ti+1,Rank(Suffix(i+2)))<(tj,tj+1，Rank(Suffix(j+2))).
上述二元组和三元组的比较方式同步骤三
接下来，我们俩证明DC3算法的时间复杂度为O(n).设对于长度为n的字符串，DC3算法执行时间为T（n），则有如下递归式：
T(n)=T(2n/3)+O(n)
其中，T（2n/3）是递归时间复杂度，O(n)是步骤三和四的时间复杂度。由于2/3<1,故该级数收敛，其极限为2,因此，时间复杂度为O(n).