第2章 字串比對演算法#

字串比對（string matching）是文字演算法的核心問題：給定一段文本 T（長度 n）與一個樣式 P（長度 m），找出 P 在 T 中所有出現的位置。這個看似簡單的問題，支撐著搜尋引擎、病毒碼掃描、程式編輯器的搜尋功能，以及後面章節的所有索引與過濾系統。本章從最直覺的演算法出發，逐步介紹三個經典解法，讓讀者理解「如何利用樣式本身的資訊，減少重複比較」。

2.1 節先以樸素比對建立問題的基準解法（O(nm)），再介紹用滾動雜湊加速的 Rabin-Karp 演算法；2.2 節介紹 KMP 演算法，它利用失敗函數在前綴失配時跳過不必要的比較，達到 O(n+m)；2.3 節介紹 Boyer-Moore 演算法，從右往左比對配合「壞字元」與「好後綴」規則，實務上常常遠快於理論下界。

學完本章，讀者應能依情境選擇合適的比對演算法，並理解這些演背後「預處理樣式、換取查詢加速」的設計哲學。