策略的轉變：預處理文字
這個段位至今的每個方法都有一個共同習慣：花一點時間研究「模式」，然後把文字掃一遍。KMP 預先算出前綴失敗表，Z 演算法建出 Z 陣列，Rabin-Karp 用滾動雜湊——但在它們全部當中，每次搜尋都要重新讀一遍文字。當文字不斷變動、而模式固定時，這正是對的。本篇要探討的是鏡像反過來的情形，而它同樣常見：「文字」固定，卻一再被查詢。一段你會用上千個模式去探測的基因組；一本你會搜上一百次的書。當穩定的那一邊是文字時，改去預處理「它」才划算。
這把大傘底下住著兩個不同的目標，把它們分清楚會很有幫助。第一個：你有許多模式，想在掃過文字一遍時就找出它們「全部」——這是「多模式」問題，由 Aho-Corasick 解決。第二個：你有一段文字，想幾乎瞬間回答關於它的「任何」未來子字串問題——模式 P 出現了嗎？出現幾次？在哪裡？——這是「文字索引」問題，由後綴樹及其更扁平的表親後綴陣列解決。目標不同，但心態上的轉變相同：在文字上預先付出一筆成本，好讓之後每次查詢都便宜。
Aho-Corasick：長成一棵樹的 KMP
假設你必須一次在一段文字裡掃找一整本字典的單字——比如 {he, she, his, hers}。對每個單字分別跑 KMP，意味著每個單字都要重讀一遍文字，對 k 個模式、長度 n 的文字要花 O(k*n)。Aho-Corasick 基本上只用一趟就全部搞定。第一個材料是字典樹：把所有模式黏進單一棵樹，讓共用前綴共用一條路徑。「he」、「hers」與「his」都從同一個 h 節點起步；「hers」只是把「he」那條路徑再延長。每個節點標記是否有某個模式在此結束。現在想像把文字一個字元一個字元餵進來，沿著字典樹往下走——只要字元持續比對，你就下降，而每當你落在一個被標記為模式結尾的節點上，你就找到了一次出現。
但當下一個字元在字典樹裡「比對失敗」時會怎樣？這就是漂亮的地方，而且是純粹的 KMP 思路。你不會退回根節點、把已比對的一切都浪費掉，而是順著一條「失敗連結」走到「另一個」最深的字典樹節點，使它的標籤是你當前位置的真後綴。這正是失敗函數那篇的前綴失敗想法，從單一字串提升到一棵樹上：當你無法延伸一個比對時，退回到「同時也是某個模式前綴」的最長已比對後綴，並從那裡繼續，不必重讀文字。這些失敗連結用一趟對字典樹的廣度優先掃描建好一次，每個節點的連結由它父節點的連結算出——正是填滿 KMP 表格的那同一套自我引導遞迴，如今在一棵樹上開枝散葉。
回報很乾淨。建造這台自動機所花的時間，正比於所有模式的總長度，記作 m；掃描文字是 O(n) 再加上回報比對的成本；所以整件工作是 O(m + n + z)，其中 z 是找到的比對數。最後那個 z 項既無可避免又誠實——如果存在一百萬個比對，你就必須花時間列出一百萬個比對，沒有任何演算法躲得過這筆輸出成本。把它和「分別跑每個模式」的天真 O(k*n) 比一比：Aho-Corasick 把那個 k 倍因子換成單獨一趟掃描，這正是為什麼它驅動著入侵偵測規則集、以及同時獵捕上千個特徵碼的病毒掃描器。
後綴樹：一次為每個子字串建索引
現在來看第二個目標：一段固定文字 T，被許多未來的模式查詢。關鍵的觀察雖小卻有力——「T 的每個子字串都是 T 某個後綴的前綴」。「banana」裡的子字串「ana」是後綴「anana」（也是後綴「ana」）的開頭。所以如果我們建出一個結構，能讓我們從頭沿著任一後綴往下走，就能藉由把模式一個字元一個字元地走過去來測試任何模式：若走得通，模式就出現了。後綴樹正是這樣——T 全部 n 個後綴組成的一棵字典樹，但經過壓縮，使任何一串只有單一子節點的鏈塌縮成一條以「整段子字串」標記的邊。這種壓縮正是它不致爆炸的原因：未壓縮的後綴字典樹可能有 Theta(n^2) 個節點，但壓縮後的樹至多有 2n 個節點，因為一棵有 n 個葉子、且沒有單一子節點的內部節點的樹，至多有 n-1 個內部節點。
樹一旦存在，查詢就美極了。要測試模式 P（長度 p）是否出現在 T 中，只需把 P 從根往下走，沿著邊的標籤逐字比對。若中途卡住，P 就不出現。若走完，P 就出現——而你停下之處底下的每個葉子，都對應 P 在 T 裡的一個起始位置，所以「數出現次數」就是「數一棵子樹裡的葉子」，而「定位它們」就是「把那些葉子列出來」。這一切花 O(p + occ)，與整段文字的長度 n 無關。再讀一遍：在一次性建好之後，問「這個模式在這裡嗎？」所花的時間正比於「模式」，而非文字。在十億字元的基因組裡搜一個 20 字元的探針，只碰約 20 個字元。這正是值得為一個索引付費的全部理由。
誠實的麻煩在於建造。後綴樹可以用巧妙的演算法在 O(n) 時間內建好（Ukkonen 的線上建構法是經典），但它們確實精巧難懂，而且這棵樹背負沉重的常數：每個節點都需要子節點指標和後綴連結，所以實際記憶體用量常達每字元 15 到 40 位元組——對一段大文字是個真實的負擔。線性的時間界是真的、也很美，但這裡的「O(n)」藏著一個肥大的常數，又一次提醒我們：漸進描述的是縮放，而非你機器實際付出的位元組。那筆記憶體成本，正是促使我們轉向下一個更精瘦結構的不適。
後綴陣列：同樣的威力，少得多的記憶體
後綴陣列保留了後綴樹幾乎全部的查詢威力，卻把它幾乎全部的笨重給扔掉。這個想法簡單得讓人卸下心防：取 T 全部 n 個後綴，按字典序（就像字典裡的順序）排序，然後只存它們「起始位置」依排序後順序排成的陣列。對「banana$」，排序後的後綴是 $、a$、ana$、anana$、banana$、na$、nana$，而後綴陣列就是它們起始索引的清單。就這樣——一個有 n 個整數的陣列，每個通常 4 位元組，所以總共約 4n 位元組。沒有子節點指標，沒有節點物件，只是一個扁平的陣列。它是把後綴樹的資訊壓進一個清單，這正是為什麼記憶體吃緊時人們會伸手去拿它。
搜尋利用陣列的有序性。因為後綴按字典序排列，所有「以」模式 P「開頭」的後綴都坐在一個連續的區塊裡——於是對陣列做二分搜尋就能找到那個區塊。樸素的二分搜尋在 O(log n) 個步驟的每一步，把 P（長度 p）和一個後綴比較，得到每次查詢 O(p log n)：比後綴樹的 O(p) 稍慢一點，但為了那巨大的記憶體節省，通常是一筆划算的交易。區塊的寬度就是出現次數，裡頭的陣列項就是它們的位置。為了把後綴樹免費給出的那些結構捷徑找回來，後綴陣列會搭配一個 LCP 陣列——相鄰兩個排序後後綴之間的最長共同前綴長度。有了 LCP 陣列，二分搜尋就銳化回 O(p + log n)，而許多樹式的查詢也能在這個扁平佈局上做到。
這個陣列能多快建好？天真地排序 n 個後綴，意味著對長達 n 的字串做 n 次比較，是嚇人的 O(n^2 log n)。但後綴彼此大量重疊，這份冗餘是可以利用的：經典的「前綴倍增」法先按前 1 個、再前 2 個、再前 4 個……字元排序，重用先前的名次，達到 O(n log n)；而且還有線性時間的 O(n) 建構法（DC3／skew 演算法是著名的一個）。LCP 陣列接著可用 Kasai 演算法在 O(n) 內建好。所以實務上，一個後綴陣列加上 LCP 陣列，用幾個整數陣列就給了你後綴樹等級的文字索引，而記憶體只是其一小部分——這正是為什麼從生物資訊到全文搜尋的真實系統裡，當主力的是它、而不是那棵樹。
選擇你的工具，以及這個段位通往何方
讓問題來挑工具。許多模式、對一段串流文字掃一次、在它們飛過時全部找出：Aho-Corasick，O(m + n + z)。一段你會用新模式一查再查的文字：一次性建好一個索引。如果你負擔得起記憶體、又想要最簡單最快的查詢，後綴樹給你 O(p) 的查找；如果記憶體要緊——而在規模化時幾乎永遠要緊——搭配 LCP 陣列的後綴陣列，用大約四分之一的佔用空間，給你幾乎相同的威力。而如果文字在兩次查詢之間會變動，這些索引都無法乾淨地套用；你會退回到前幾篇指南的「預處理模式」方法，那些方法每次都重新讀一遍文字。
Pattern fixed, text changes -> KMP / Z / Rabin-Karp O(n) per search Many patterns, text scanned once -> Aho-Corasick O(m + n + z) Text fixed, many later queries -> suffix tree build O(n), query O(p + occ) ... same, but memory matters -> suffix array + LCP build O(n log n)/O(n), query O(p log n)
退一步，注意那些貫穿其中的統一線索。Aho-Corasick 就是 KMP 的失敗函數想法，分枝到一棵字典樹上——舊智慧被帶進新形狀。後綴樹與後綴陣列都立基於同一個觀察：子字串是後綴的前綴，一次用指標攻克、一次用排序攻克。而這些結構中的每一個，都是你在這整條學習階梯上一再遇見的同一場策略性賭注的實例：預先付出一筆成本，好讓之後如洪水般的操作變得便宜——這正是預處理、字典樹與索引背後的全部邏輯。誠實的但書也與這門課其餘部分押韻——後綴樹的 O(n) 建造藏著沉重的記憶體常數，每次查詢的界限假設索引已經建好，而那個 +z 或 +occ 項是真正產出答案無可避免的代價，不是一個該被優化掉的缺陷。
這就為「字串與文字」這個段位收尾。從暴力比對誠實的 O(n*m)，經過 KMP 與 Z 演算法的線性掃描，越過 Rabin-Karp 的雜湊賭注，到字典規模的 Aho-Corasick 與基於後綴的索引，你現在擁有一套工具箱，能從單次搜尋一路擴展到永遠被查詢的語料庫。再往前是值得日後一看的近親——後綴自動機，它把每個子字串都辨認成一台小小的有限機器，以及序列比對，那裡的比對變成近似的，並與前幾段的編輯距離動態規劃相遇。同一份直覺貫穿始終：搞清楚什麼是固定的，決定要預處理什麼，並對每個界限究竟為你買到了什麼保持誠實。