Home - 数学杂记

“伟大的事业使根源于坚持不断地工作，以全副精神去从事，不避艰苦”
—— 罗素

我们回忆一下后缀数组 (Suffix Array) 的定义。给定一个字符串，譬如s="GACCCACCACC"s="GACCCACCACC"，那么他有 11 个后缀。我们对它们进行排序，然后构建后缀数组 SA 如下：

\begin{align*} & s_0=GACCCACCACC && s_8=ACC && SA[0]=8 \\ & s_1=ACCCACCACC && s_5=ACCACC && SA[1]=5 \\ & s_2=CCCACCACC && s_1=ACCCACCACC && SA[2]=1 \\ & s_3=CCACCACC && s_10=CC && SA[3]=10 \\ & s_4=CACCACC && s_7=CACC && SA[4]=7 \\ & s_5=ACCACC && s_4=CACCACC && SA[5]=4 \\ & s_6=CCACC && s_9=CC && SA[6]=9 \\ & s_7=CACC && s_6=CCACC && SA[7]=6 \\ & s_8=ACC && s_3=CCACCACC && SA[8]=3 \\ & s_9=CC && s_2=CCCACCACC && SA[9]=2 \\ & s_{10}=C && s_0=GACCCACCACC && SA[10]=0 \end{align*}

实际上，我们有办法让这个排序做到O(n)O(n) 的复杂度。
这不违反直觉，因为后缀之间的比较包含了大量重复的信息。
下面介绍 Skew Sort 算法，在O(n)O(n) 的时间内完成对所有后缀的排序。

第一步，我们根据后缀起始位置对 3 的余数，进行分组

S0 = 0 : GACCCACCACC
     3 : CCACCACC
     6 : CCACC
     9 : CC
S1 = 1 : ACCACCACC
     4 : CACCACC
     7 : CACC
     10: C
S2 = 2 : CCCACCACC
     5 : ACCACC
     8 : ACC

然后呢，我们把S1,S2S1,S2 组内的后缀拿出来，并且每个后缀只取前三个字符，这样构建出了一个新的字符串S12S12:

       1     4     7    10     2     5     8
S12 = ACC | CAC | CAC | C$$ | CCC | ACC | ACC

因为这个字符串每一位只有 3 个字符，我们可以考虑用基数排序在O(n)O(n) 的时间内完成对他们的排序。排序结果如下：

       1     4     7    10     2     5     8
S12 = ACC | CAC | CAC | C$$ | CCC | ACC | ACC
       0     2     2     1     3     0     0

这一步需要注意，我们允许重复的排序。

然后我们把原来的 S12 替换成一个新的字符串，也就是排序结果作为字符：

S12 = 0 2 2 1 3 0 0

注意到这个 S12 字符串的长度显然=7≈2n3=7\approx\frac{2n}{3}，我们递归调用 Skew Sort 算法来求出一个 S12 的后缀数组，以及对应的原字符串：

 SA'[0] = 6   |   S12[6] = 0        |   ACC
 SA'[1] = 5   |   S12[5] = 00       |   ACCACC
 SA'[2] = 0   |   S12[0] = 0221300  |   ACCCACCACC$$...
 SA'[3] = 3   |   S12[3] = 1300     |   C$$...
 SA'[4] = 2   |   S12[2] = 21300    |   CACC$$...
 SA'[5] = 1   |   S12[1] = 221300   |   CACCACC$$...
 SA'[6] = 4   |   S12[4] = 300      |   CCCACCACC

然后，我们把 SA’映射到一个新的数组 A，利用之前的表：

       1     4     7    10     2     5     8
S12 = ACC | CAC | CAC | C$$ | CCC | ACC | ACC
       0     2     2     1     3     0     0

可以映射为：

 SA'[0] = 6 -> A[0] = 8
 SA'[1] = 5 -> A[1] = 5
 SA'[2] = 0 -> A[2] = 1
 SA'[3] = 3 -> A[3] = 10
 SA'[4] = 2 -> A[4] = 7
 SA'[5] = 1 -> A[5] = 4
 SA'[6] = 4 -> A[6] = 2

也就是考虑 S12 = 0221300 这个字符串中，每一个后缀在原来字符串中的位置。譬如 SA’[0]=6，那么在 S12 中，第 6 位对应了原始字符串 s8 后缀。

这个 A 数组，其实包含了所有原字符串所有模 3 余 1、模 3 余 2 的后缀的排序信息。

因为 0221300 这个字符串，其实 encode 了原先后缀前三个字符间的大小关系。

接下来，我们考虑排序 S0 中的后缀。这时候的排序有点技巧！

我们只需要按照 S0 中，每个后缀的第一个字符排序！如果第一个字符相同时，我们就把它们加一，然后在 A 数组里查询！因为 A 数组包含了模 3 余 1、模 3 余 2 的后缀排序信息，所以模 3 余 0 的后缀去掉第一个字符后，一定会落在这里面。

延续之前的例子，我们考虑 s0, s3, s6, s9 这四个后缀。首先我们把它们下标都加一，考虑 s1, s4, s7, s10。根据 A 数组，我们知道 s1, s4, s7, s10 的相对顺序是：

 s1 < s10 < s7 < s4

因此我们先确定顺序： s0, s9, s6, s3。

然后我们根据它们的首字符进行基数排序，在首字符相同时，不改变相对顺序。因为去掉首字符后的部分已经按照 s1 < s10 < s7 < s4 的顺序排好了！

我们把模 3 余 0 的后缀排序结果放在 B 数组中：

 B[0] = 9 = CC
 B[1] = 6 = CCACC
 B[2] = 3 = CCACCACC
 B[3] = 0 = GACCCACCACC

最后，我们考虑合并 A、B 数组，获得原数组的一个后缀排序。 这时候可以考虑归并排序。

对于一个模 3 余 1 或 2 的后缀，和一个模 3 余 0 的后缀，我们首先比较它们的首字符，如果不相同那么直接确定了顺序。

否则的话，我们可以考虑把它们同时后移一位，就变成了比较一个模 3 余 2 或 0 的后缀，和一个模 3 余 1 的后缀。

如果此时是 模 3 余 2 和 模 3 余 1 的后缀比较，因为它们都在 A 数组中，A 已经是有序的了，所以可以直接出结果。

否则就是 模 3 余 0 和 模 3 余 1 的后缀比较，我们再次比较首字符，如果不同的话再后移一次。

这样就变成 模 3 余 1 和 模 3 余 2 的后缀比较了，这一定能在 A 数组里查询出来。

因此归并时，比较的时间是常数的！最多后移两次，就可以一定利用已有的排序信息 A 了。这也是模 3 的妙处。

最后我们得到的后缀数组就是：

 SA[0] = 8
 SA[1] = 5
 SA[2] = 1
 SA[3] = 10
 SA[4] = 7
 SA[5] = 4
 SA[7] = 9
 SA[8] = 6
 SA[9] = 3
 SA[6] = 2
 SA[10]= 0

因此总的时间复杂度其实满足T(n)=T(2/3n)+O(n)T(n)=T(2/3n)+O(n)，根据主定理T(n)=O(n)T(n)=O(n)。