Linear time Suffix Array Construction: DC3 算法

如果說 string matching 可以在 linear time 完成有點反直觀,
我覺得可以在 linear time construct Suffix Array 更加神奇

雖然很久以前已經有 linear time 做法, 不過好像都是先 build suffix tree 再 traverse
DC3 algorithm 是個簡單, 優美的算法, 而且還挺新的 (2003)
如果投票「十大最喜歡的算法」應該會有一席位

Step 1: 目標是對 suffix[x] 排序, x mod 3 = 1 or 2

設 s1 = suffix[1], s2 = suffix[2] (0 based)
如果 s1, s2 的長度不是 3 的倍數, 在最後補 0

然後每 3 個 character merge 成一個 tuple
使用 radix sort 計算它們的 rank (有機會相同)
假設沒有 ties 的情況出現, 則它們的 rank 便是這個 step 的目標

如果有 ties 出現, construct s' = r1 + 0 + r2
r1 和 r2 為那些 tuple 的 rank
然後 recursive 找出 s' 的 suffix array, 留意 s' 的長度為 2N/3

經過 step 1 後, 已有 information = suffix[x] 之間的相對排序 (x mod 3 = 1 or 2), 記為 R

Step 2: 目標是對 suffix[x] 排序, x mod 3 = 0

只要對每個 suffix[3i] construct tuple(s[3i], R[3i+1])
再使用 radix sort 便可

Step 3: merge step 1, 2 的結果!

最後一個 step
難處是比較 suffix[3i] 和 suffix[3j+1] 之類
但其實做法很簡單, 只要寫成

suffix[3i] = tuple(s[3i], R[3i+1])
suffix[3j+1] = tuple(s[3j+1], R[3j+2])

由於 R[3i+1] 和  R[3j+2] 可以直接比較, 問題迎刃而解
和 suffix[3j+2] compare 時方法相似, 不過是 3-tuple

DC3 算法的 time complexity:

T(N) = O(N) + T(2N/3)
T(N) = O(N)

References: Linear Work Suffix Array Construction