[ Difference Cover modulo 3, DC3 ] 後綴數組線性DC3演算法

DC3 是歷史上第一個線性時間的後綴數組演算法，而且相對於 SA-IS 來說更容易作為教材。

這是 DC3 的原始論文：
https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf

首先是後綴分類。我們會將所有後綴根據其起始位置 $i$ 對 3 的餘數進行分類，形成三種不同的類型：

• Type A ($i$%3=0):
  這類後綴的起始位置是 3 的倍數。它們不會直接參與初始排序，而是透過 Type B 的排序結果間接排序。
• Type B1 ($i$%3=1):
  這類後綴會與 Type B2 一起組成 Type B 後綴集合，並進行初步排序。
• Type B2 ($i$%3=2):
  同樣屬於 Type B 後綴集合，與 B1 一起進行排序。

以 "mississkp" 為例，為了方便操作我們在其尾端加入兩個哨兵字元 '\0'。

如圖1 所示，首先我們對於每個 Type B 後綴，我們取出其前三個字元作為排序鍵值，將這些三元組視為新的字元（透過 radix sort 將三元組映射為整數，實作上呼叫了三次 counting sort），並對它們進行排序。若排序後的鍵值唯一，則排序完成；否則需將這些鍵值壓縮成新的字母表，並遞迴呼叫 DC3 來排序這個縮小版的問題。

圖1

如圖2 所示，此時 Type B 後綴的排名已經確定了。對於每個 Type A 後綴 i，我們無法直接比較整個後綴（因為效率問題），但可以利用 Type B 的排名來構造一個排序鍵值：

• 對於每個 Type A 後綴 i，我們取：

• $S[i]$：當前字元
• $R[i+1]$：Type B1 後綴的排名（因為 i+1 % 3 = 1）

一次 counting sort 後，我們得到了  Type A 後綴的排名。

圖2

接著我們要合併兩種後綴的排序結果，可以使用 std::merge 合併，但須要寫一個 $\ord{1}$ 的比較函數。設比較函數 $cmp(x,y)$， $x$ 是某個 Type B 後綴的編號，$y$ 是某個 Type A 後綴的編號：

1. $S[x]\ne S[y]$：
   直接比較 $S[x],\;S[y]$
2. Type B1 後綴 ($x$ % 3 = 1)：
   此時 $x+1$ 和 $y+1$ 都是 Type B 後綴，直接比較 $R[x+1],\;R[y+1]$
3. Type B2 後綴 ($x$ % 3 = 2)：
   此時 $x+1$ 是 Type A 後綴， $y+1$ 是 Type B 後綴，直接呼叫 $!cmp(y+1,x+1)$

圖3 展示了當前範例的合併結果，DC3 算法到這邊就結束了。

整體時間複雜度 $T(n)=T(2n/3)+\ord{n}=\ord{n}$，但要注意空間使用量
$$M(n) =
\begin{cases}
n + \delta(n) + 2, & n \leq 2 \\
n + \delta(n) + 2 + M\left(\left\lfloor \frac{2(n + \delta(n))}{3} \right\rfloor\right), & n > 2\end{cases}\\ \delta(n) = [n\equiv 1\left(\bmod 3\right)]$$

根據 AI 的推導 $M\left(n\right)\le 3n+\left\lfloor 4\log_{1.5}\left(n-2\right)\right\rfloor+1$。

圖3

2025/10/10 更新：有人發現我原始的程式碼在當 n%3=1 遞迴時在 Type B1 和 Type B2 之間沒有隔離符號，有可能導致這兩類後綴排序錯誤，聽說我一開始的參考資料 ([2009] 后缀数组——处理字符串的有力工具 by. 罗穗骞) 也有一樣的問題，因此我花了點時間重寫了 DC3 的教學。

錯誤原因如圖4 所示，若不加上這個哨兵字元的話，後綴 7 就不會被加入遞迴運算，這樣會導致某個 Type B1 後綴將不是自己正確後綴的 Type B2 後綴連接起來排序導致結果錯誤。

圖4

以下提供模板(註解是請 AI 寫的，拿掉之後程式碼應該會很短):