後綴陣列（suffix array）
後綴樹很強大但笨重。後綴陣列是同一個想法被壓扁成一串純數字。取一個字串的每個後綴，把它們全部按字母順序排好，然後只記下它們在這個排好的順序中的起始位置。這一小串整數——沒有樹、沒有指標——就捕捉了所有後綴的字典序結構，並以零頭的記憶體支援快速模式搜尋以及更多功能。
形式上，長度為 n 的字串 S 的後綴陣列 SA 是位置 0..n-1 的一個排列，使得起始於 SA[0]、SA[1]、...、SA[n-1] 的後綴依字典序（辭典順序）遞增。對 "banana"，排好的後綴是 "a"、"ana"、"anana"、"banana"、"na"、"nana"，所以 SA = [5,3,1,0,4,2]。由於後綴已排序，模式 P 的每一次出現都對應陣列中一段連續的區塊（所有以 P 開頭的後綴都聚在一起），所以你能用兩次二分搜尋找到那個區塊，得到 O(m log n) 的比對——或在輔助的 LCP 陣列下達 O(m + log n)。樸素地用排序字串來建後綴陣列是 O(n^2 log n)，但專門的演算法（O(n log n) 的前綴倍增法，或 O(n) 的 SA-IS 與 DC3 演算法）能高效建構它。這個陣列只用 O(n) 個整數，每個或許 4 位元組，遠少於後綴樹。
後綴陣列是全文搜尋索引、Burrows-Wheeler 轉換（bzip2 的核心，以及基因比對器所用 FM-index 的核心）、最長共同子字串查詢和相異子字串計數背後的主力。配上它的搭檔 LCP 陣列，後綴陣列基本上能做後綴樹所能做的一切，且常數更好、快取行為好得多，這正是它在實務上稱霸的原因。取捨在概念層面：有些操作在樹上描述更自然，而你要從陣列加 LCP 資訊重建那種樹狀推理，而不是直接讀出來。
S = "banana"，SA = [5,3,1,0,4,2]。要搜尋 P = "ana"：用二分搜尋找出以 "ana" 開頭的後綴範圍。它們是在 SA 位置 1 和 2 的那些（後綴 "ana" 起始於索引 3、"anana" 起始於索引 1），所以 "ana" 出現在文字位置 3 和 1。一段連續的 SA 區塊就等於完整的出現集合。
後綴排好序後，任何模式的出現都形成一段連續區塊，可用二分搜尋找到。
純後綴陣列給 O(m log n) 搜尋；配上 LCP 陣列可達 O(m + log n) 並重現後綴樹式查詢。大輸入時不要把後綴當字串來排序——那是 O(n^2 log n)；請用正確的 O(n log n) 或 O(n) 建構法。