從比較字母到比較數字
本輪的第一篇導覽衡量了 暴力比對 的代價：在 n - m + 1 個對齊位置的每一個上，你都要重新比較最多 m 個字元，最壞情況是 O(n*m)。KMP 與 Z 演算法 之所以勝過它，是因為它們從不重讀已經理解過的字元。拉賓-卡普演算法 從一個完全不同的角度攻擊同一個問題：它不是在字元上變得更聰明，而是乾脆不再一個一個地看字元。它把文字的每一扇長度為 m 的視窗總結成「一個數」，再拿這個數去和模式字串的數比對。
這個數叫做 雜湊值，在這個情境下也叫 指紋。這筆交易令人無法抗拒：比較兩個數是一次運算，無論 m 多長；而比較兩個長度為 m 的字串卻要花上最多 m 次運算。如果我們能把模式字串的指紋算一次、又能廉價地算出每一扇文字視窗的指紋，那麼多數對齊位置只要一次整數比較就能被排除。整個技巧的成敗全繫於一個問題——我們能不能在不重讀視窗全部 m 個字元的情況下，得到它的指紋？
滾動雜湊的遞迴式
這裡是賦予 滾動雜湊 其名的巧妙之處。把每個字元看成 b 進位下的一位數（把 b 想成字母表大小，比如 256），再把一扇視窗讀成那個進位制底下的一個數。視窗 c_0 c_1 ... c_(m-1) 變成值 c_0*b^(m-1) + c_1*b^(m-2) + ... + c_(m-1)。從頭算這個值要花 O(m)。但當視窗向右滑一格時，新的值幾乎就是舊的值：我們只是丟掉最左邊那一位、又在最右邊接上新的一位，就像汽車里程表翻轉一樣。
H(window starting at i+1)
= ( H(window at i) - text[i]*b^(m-1) ) * b + text[i+m]
drop the leftmost digit, shift left one place, add the new digit減去離開的字元的貢獻（它的位值乘以 b^(m-1)），把整體乘以 b 好讓每個剩下的位數都往上移一格，再加上抵達的字元。這是固定的少量運算，所以每次滑動是 O(1)，而在為第一扇視窗做 O(m) 的暖身之後，算出全部 n - m + 1 個視窗的雜湊值總共只花 O(n)。其中 b^(m-1) 是一個我們預先算好一次的常數。這就是引擎；其餘的一切都只是為了讓引擎保持誠實的記帳工作。
為何我們在質數的模下運算
遞迴式裡藏著一個問題：對 256 個字母的字母表、長度 50 的模式而言，b^(m-1) 是個天文數字般大的整數。對那麼大的數做任意精度算術，本身每次運算就要花 O(m)，會把整個加速毀掉。解法是讓每一步計算都在某個固定的數 M 之下取模，使每個值都保持在單一個機器字內。我們把 M 取成一個大 質數，而且通常把底數 b 在 1 到 M - 1 的範圍內隨機選取。
選擇質數模有兩個理由，兩者都值得理解、而非死記。其一，模算術在這裡之所以好用，是因為加法與乘法和取餘數可以交換——(x*b + c) mod M 能夠一步一步算出來，從不需要組成那個巨大的真值。其二，也更深一層，選一個質數 M 配上隨機選取的底數，能讓雜湊值均勻散開，並讓我們得以證明一個很小的碰撞機率：兩扇相異視窗碰撞這件事，化成了質數模下的一個多項式方程式，而一個非零的 m 次多項式在那個體裡至多有 m 個根。當 M 遠大於 m 時，隨機底數恰好命中某個根的機會微乎其微。
碰撞，以及兩個誠實的版本
現在我們正面迎擊那份有損性。當一扇視窗的雜湊值等於模式的雜湊值時，那是一個「候選」，不是已確認的比對。真正的比對一定會產生相等的雜湊值，所以我們永遠不會漏掉一個真實的出現；但一個不同的字串可能意外地共用那個雜湊值——一次 碰撞——若你盲目相信它，它就會是一個假警報。處理這件事有兩種有原則的辦法，它們分別坐落在本階梯稍早介紹過的一個經典取捨的兩側。
- 拉斯維加斯式（永遠正確）：每遇到一次雜湊相符，就比對實際的 m 個字元來驗證。確認的比對才回報；碰撞會被發現並丟棄。答案永遠完全正確；只有執行時間是隨機的，取決於驗證得清理掉多少個假的雜湊相符。
- 蒙地卡羅式（永遠快）：相信每一次雜湊相符就是真比對，從不驗證。每個回報的位置都是真比對，除非有碰撞騙了我們，所以演算法以一個有保證的 O(n + m) 執行，但極少數情況下可能回報一個偽陽性。
會驗證的版本是一個 拉斯維加斯演算法；不驗證的版本是一個 蒙地卡羅演算法。用一個接近 2^61 的隨機質數模，任一特定碰撞存活下來的機率約為 m/M，小到幾乎消失，所以拉斯維加斯版的期望執行時間是 O(n + m)：暖身加上滑動，再加上期望中寥寥幾次的驗證。然而最壞情況仍是 O(n*m)——若有個對手（或純粹的壞運氣）使每一扇視窗都與模式雜湊相符，那麼每個對齊位置都會觸發一次完整的 O(m) 驗證。就像隨機快速排序，那個好的界是個「期望」界，不是最壞情況的保證。
拉賓-卡普何處出色，何處不然
如果 KMP 給的是一個無隨機性、無偽陽性的決定性 O(n + m)，那為什麼還要動用拉賓-卡普？因為滾動雜湊能推廣到前綴函數技巧推廣不到的地方。一次搜尋「許多」模式是最出名的情形：把每個共同長度的模式雜湊進一個集合裡，然後讓單一個滾動雜湊掃過文字，以 O(1) 查每一扇視窗——當所有模式長度相同時，這比實作 Aho-Corasick 簡單得多。它也自然延伸到二維的模式比對（在一個大方格裡尋找一個小方格），那是線性字串方法處理起來不夠優雅的。
滾動指紋也是超越比對之外、可重複利用的機械。雜湊過的子字串，讓你在 O(n) 的預處理之後以 O(1) 回答「文字的這兩段範圍相等嗎？」，這是許多競技程式設計與生物資訊任務的基石；而其底下的模算術，正是你在數論那一輪遇過的 快速模冪 世界。比較指紋以檢驗相等，在觀念上和像 米勒-拉賓 這樣的隨機質數測試是同一個想法：用一個便宜的、只以可控的微小機率出錯的機率性檢查，去取代一個昂貴的精確檢查。
不過，對代價要誠實。拉賓-卡普的優雅建立在幾個假設上：機器字上的算術是 O(1)（用單一個質數模就是為了忽略巨數的代價，這正是我們採用它的原因），以及輸入不是針對你的固定參數刻意設計的。一個知道你的底數與模數、且鐵了心的對手，能製造出最壞情況的碰撞，這就是為什麼底數的隨機選取必須保密，才能享有那個期望界。對於一個沒有這些顧慮的單一短模式，KMP 或 Z 演算法通常是更乾淨、無依賴的選擇；當許多模式、範圍相等查詢、或更高維度進入畫面時，拉賓-卡普才賺到它的位置。