BZOJ 1031 [JSOI2007] 字符加密：Burrows-Wheeler 變換與後綴數組

題目大意

給定一個字符串 S（長度 ≤ 100,000），將其視為環狀字符串，列出所有 n 個循環移位，按字典序排序，取每行最後一列字符拼接，即為加密結果（即 Burrows-Wheeler 變換 BWT）。

經典例子

原串: JSOI07
循環移位:
JSOI07
SOI07J
OI07JS
I07JSO
07JSOI
7JSOI0

字典序排序:
07JSOI
7JSOI0
I07JSO
JSOI07
OI07JS
SOI07J

最後一列: I 0 O 7 S J → "I0O7SJ"

後綴數組 O(n log n) 解法

BWT 的標準構建方法：

1. 將 S 複製兩份拼接：T = S + S（長度 2n）
2. 對 T 構建後綴數組 SA
3. 遍歷 SA，若 SA[i] < n，說明該後綴對應一個合法的循環移位（起始位置在原串範圍內）
4. 該循環移位的最後一字符即為 T[SA[i] + n - 1]（或 S[(SA[i] - 1 + n) % n]）
5. 按 SA 順序收集這些字符即為答案

關鍵代碼

// 構建 T = S + S
for (int i = 0; i < n; ++i) {
    T[i] = T[i + n] = S[i] + 1; // +1 避免 0 干擾
}
T[2*n] = 0; // 結束符

// 後綴數組構建（倍增/SA-IS）
build_sa(2*n, 128); // 字符集大小

// 輸出 BWT
for (int i = 0; i < 2*n; ++i) {
    if (SA[i] < n) {
        int pos = (SA[i] - 1 + n) % n; // 循環前一字符
        putchar(S[pos]);
    }
}

為什麼這樣做是對的？

• T 的所有後綴中，起始位置 [0, n-1] 的恰好對應 S 的所有循環移位
• 後綴數組按字典序排序了所有後綴，因此也間接按字典序排序了所有循環移位
• 循環移位 S[i...n-1] + S[0...i-1] 的最後一字符是 S[i-1]（循環意義下）

複雜度

• 時間：O(n log n)（倍增）或 O(n)（SA-IS/DC3）
• 空間：O(n)

延伸：BWT 的逆變換

BWT 是可逆的（配合原串在排序矩陣中的行號），這是 bzip2 等壓縮算法的核心。本題僅需正向變換。