後綴樹（suffix tree）

拿一個字串，把它的每一個後綴都寫下來——對 "banana" 就是 "banana"、"anana"、"nana"、"ana"、"na"、"a"。現在想像把它們全部存進一棵壓縮 trie，讓共同開頭共享路徑，長的單子節點鏈塌縮成以子字串標記的邊。那個結構就是後綴樹，它是個出奇強大的索引：一旦建好，關於這個字串、數量驚人的問題都變成往樹下走幾步的快速操作。

具體來說，長度為 n 的字串 S 的後綴樹，是一棵包含 S 全部 n 個後綴的壓縮 trie（通常給 S 加一個唯一的結尾標記如 '$'，使得沒有後綴是另一個的前綴，於是每個後綴都終結於它自己的葉子）。每條邊以 S 的一個子字串標記，每片葉子對應一個後綴，而每個內部節點對應一個至少出現兩次的子字串（一個重複的、會分岔的脈絡）。要檢查模式 P 是否出現在 S 中，只要把 P 從根往下走：若你能拼出整個 P，它就出現了，而其下的葉子精確告訴你出現在哪裡、出現幾次——所以樹建好後，比對花 O(m) 時間，與 n 無關。奇蹟在於：儘管整棵樹代表了全部 n 個總長約 n^2/2 的後綴，卻能用巧妙的演算法（Ukkonen 的是著名的線上版本）在 O(n) 時間建好、用 O(n) 空間儲存，因為共享結構被壓縮掉了。

後綴樹把一趟預處理變成一把瑞士刀：最長重複子字串（最深的內部節點）、兩字串的最長共同子字串、計算相異子字串數、找出模式的所有出現，等等——許多都在線性或近線性時間內完成。誠實的提醒是常數因子：後綴樹帶著大量指標，通常每個字元用掉 10 到 20 多個位元組，對大文字而言是實實在在的記憶體負擔。正是這個代價，使得後綴陣列（一個更扁平、對快取更友善的替代品）在實務上常被偏好，儘管後綴樹是更乾淨、更好推理的物件。