字串比對問題

把問題講清楚

在動用任何聰明方法之前，先確定我們究竟被要求做什麼。我們有一個長字串，稱為文字 T，長度為 n；以及一個短字串，稱為模式 P，長度為 m，且 m 不超過 n。精確字串比對問的是：P 以一整塊連續的形式，出現在 T 的哪些位置上？在位置 i 處的一個比對，意味著 T[i]、T[i+1]、...、T[i+m-1] 這 m 個字元，逐字元地恰好等於 P[0]、P[1]、...、P[m-1]。我們通常要的是每一個這樣的 i，而不只是第一個。

那個定義裡有兩件事非常重要。第一，比對必須是連續且對齊的：P 必須以一個不中斷的視窗整塊地蓋在 T 上，所以「ana」在「banana」裡比中兩次（位置 1 與位置 3），即使這兩個視窗彼此重疊。第二，字元來自某個字母表——允許符號的集合，例如 26 個字母、4 種 DNA 鹼基，或全部 256 個位元組值。字母表的大小悄悄地形塑了問題的難易，當比較在極小與極大字母表上開始表現得很不一樣時，我們就會看到這一點。

暴力法，以及為什麼它感覺很對

最自然的點子，也是任何人最先想到的那個。把模式沿著文字一次移動一格，在每個對齊位置逐字元檢查那個視窗是否相符，直到出現不符或完全相符為止。這就是暴力比對，是暴力法的教科書範例：總共有 n - m + 1 個可能的起始位置，那就全部試一遍、逐一驗證。它顯然正確，因為它就是在每個位置上照字面測試定義——沒有任何巧妙之處，沒有什麼好懷疑的。

for i = 0 .. n-m:           # each starting position
    j = 0
    while j < m and T[i+j] == P[j]:
        j = j + 1            # extend the match
    if j == m: report match at i

暴力比對：嘗試每個對齊位置，往後延伸直到不符或完全相符。

對日常文字而言，這常常已經夠快了。在一段英文裡找「cat」，大多數對齊位置在第一個字元就陣亡——文字上的字母不是 'c'，於是內層迴圈比一次就結束，我們便滑向下一格。當不符出現得既早又便宜時，總工作量接近 n 次比較，這也是為什麼暴力比對在真實編輯器裡做短字串搜尋時還活得好好的。不過它良好的表現是一個平均情況的故事，倚賴的是文字與模式不共享長段的結構。

暴力法在哪裡失血

麻煩出現在「差一點就成功」一再重演的時候。取文字「aaaaaaaaab」（九個 a 接一個 b）與模式「aaaab」。在第一個對齊位置，我們開心地比中四個 a，接著模式裡的 b 撞上文字裡的 a——在第五次比較時不符。我們向右滑一格，再做一模一樣的事：四個 a，然後失敗。每個對齊位置在失敗前都花掉接近 m 次比較，而對齊位置約有 n 個，於是總量爬升到大約 n 乘 m 次比較。

那個最壞情況是 Theta(n*m)，而當 m 大到 n/2 時就是 Theta(n^2)——對文字長度而言是平方的。深層的原因是「浪費式的遺忘」。當模式比中了「aaaa」然後失敗時，我們其實已經學到關於文字的一件真事：那四個字元全是 a。但暴力法把這份知識丟掉、只滑過一格，再從頭重新發現它的大部分。它一再重讀已經看過的文字字元，有時每個字元讀 m 次。資訊本來就在那裡；我們只是沒有把它留下來。

每個快速方法背後的那一個洞見

模式是我們事先就知道的，這就是那根槓桿。在我們甚至還沒看文字之前，就能單獨研究 P，找出它內部的重複——也就是模式的某個前綴等於它某一段的後綴的地方。這些自我重疊告訴我們：在某個對齊位置一發生不符的那一瞬間，部分相符之中有多少仍然保證會在我們移位之後對齊。於是我們就能把模式向前滑超過一格、有時滑很多格，而完全不冒漏掉真正比對的風險。

單獨對模式做預處理，以總結它的自我重疊——這正是 KMP演算法建立其前綴函數、Z 演算法建立其 Z 陣列的地方。
把文字掃描一遍，文字指標永不後退；遇到不符時，用預先算好的摘要把模式安全地盡量往前移。
因為每個文字字元只被檢視有限次數，搜尋階段花 O(n)，整個方法花 O(n + m)。

那個 O(n + m) 就是獎賞：線性時間，n 用來掃描文字、加上 m 用來研究模式，無論輸入多麼重複都不會有平方級的爆炸。值得停下來想想為什麼這是對的標準——你至少得把文字與模式各讀一遍才能確定答案，所以 O(n + m) 本質上是任何精確比對器所能企盼的最佳值。本階裡的快速演算法，是通往同一個線性下限的不同路徑。

這一階的地圖

不同的演算法以不同方式把這一個洞見化為機制，本階其餘部分會逐一走過它們。KMP演算法用一個前綴函數來總結模式，它對每個位置記錄「最長的、既是真前綴又是後綴的長度」，並用它做到永不重讀任何文字字元。Z 演算法則對字串自身計算「每個位置與開頭相符到多遠」，給出一個乾淨的線性比對器，也是一個你會在比對以外大量重用的工具。兩者都靠確定性的、以比較為基礎的推理達到 O(n + m)。

另外兩個點子採取了截然不同的角度。Rabin-Karp 裡的滾動雜湊把每個視窗變成一個數字，當視窗滑動時這數字能在常數時間內更新，以精確換取速度：它是一個隨機演算法，期望時間是 O(n + m)，但粗心的雜湊會發生碰撞，所以它是平均而言快、而非最壞情況有保證。同時，Aho-Corasick 把 KMP 推廣到一次搜尋多個模式，而後綴陣列與後綴樹則是預處理「文字」而非模式，使得在一次較重的建構之後，你能快速回答許多次查詢。

往上爬時，請記住一個誠實的提醒。線性界是一個最壞情況的漸進承諾，而漸進會隱藏常數；對於在普通文字裡找一個短模式，簡單的暴力掃描可能勝過 KMP，因為它的內層迴圈太便宜了，這就是隱藏常數陷阱在起作用。這一階的重點不是「花俏的總會贏」，而是你應該確切理解每個方法為你買到什麼、又付出什麼代價——好讓你在重複、對抗性或多模式的情況到來時，選對工具。