字串匹配基礎 (String Matching)#

問題定義#

在主串 (text) 中查找模式串 (pattern) 的位置。

主串：  "ABABDABACDABABCABAB"
模式串："ABABC"
結果：  位置 10

BF 演算法（暴力匹配）#

思路#

逐一比較，失敗時模式串後移一位。

fun bfSearch(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length

    for (i in 0..n - m) {
        if (text.substring(i, i + m) == pattern) {
            return i
        }
    }

    return -1
}

複雜度#

• 最差：O(n × m)
• 平均：接近 O(n)（實際字串很少連續匹配後失敗）

適用場景：主串和模式串都很短時，BF 夠用且實作簡單。

RK 演算法（Rabin-Karp）#

核心思想#

用雜湊值代替字元逐一比較。

步驟#

1. 計算模式串的雜湊值
2. 滑動視窗計算主串子串的雜湊值
3. 雜湊值相等時再逐字元驗證（避免雜湊碰撞）

滾動雜湊#

假設字串 "abc"，進位制 d = 26

hash("abc") = a×26² + b×26 + c

滑動到 "bcd"：
hash("bcd") = (hash("abc") - a×26²) × 26 + d

fun rkSearch(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length
    if (m > n) return -1

    val d = 26L                // 字元集大小
    val q = 1_000_000_007L     // 大質數避免溢位

    // 預計算 d^(m-1) mod q
    var h = 1L
    repeat(m - 1) { h = h * d % q }

    // 計算模式串和第一個視窗的雜湊值（用 Long 保存，避免 Int 溢位）
    var pHash = 0L
    var tHash = 0L
    for (i in 0 until m) {
        pHash = (d * pHash + pattern[i].code) % q
        tHash = (d * tHash + text[i].code) % q
    }

    for (i in 0..n - m) {
        if (pHash == tHash) {
            // 雜湊相等，逐字元驗證
            if (text.substring(i, i + m) == pattern) {
                return i
            }
        }

        // 滾動計算下一個雜湊值
        if (i < n - m) {
            tHash = (d * (tHash - text[i].code * h) + text[i + m].code) % q
            tHash = (tHash + q) % q  // 處理負數
        }
    }

    return -1
}

複雜度#

• 平均：O(n)
• 最差：O(n × m)（大量雜湊碰撞時）

注意：

• 選擇好的雜湊函式減少碰撞
• Kotlin 的 Int 只有 32 位，雜湊值要用 Long 並持續取模，否則模式串一長就會溢位

演算法比較#

進階演算法預告：

• BM：利用「壞字元」和「好後綴」規則跳過更多字元
• KMP：利用模式串自身的重複特性，失敗時跳到最佳位置

統一視角：字串匹配就是在有限狀態機上跑#

前面的演算法看似各有各的技巧，但 KMP、AC 自動機這類「線性掃描」演算法，骨子裡其實是同一件事：把模式串「編譯」成一台有限狀態機 (DFA, Deterministic Finite Automaton)，然後讓主串的字元一個一個去驅動狀態轉移。

狀態機怎麼描述匹配#

把匹配過程想成一台機器：

• 狀態：代表「目前已經匹配到模式串的哪個前綴」。狀態 0 表示一個都還沒對上，狀態 m（模式串長度）表示完全匹配。
• 轉移：每讀入主串的一個字元，就根據「目前狀態 + 這個字元」跳到下一個狀態。
• 接受狀態：一旦走到狀態 m，就代表在這個位置匹配成功。

模式串 "ABABC" 的狀態流：

0 --A--> 1 --B--> 2 --A--> 3 --B--> 4 --C--> 5(接受)

主串只需從頭掃到尾、每個字元觸發一次轉移，全程不回頭——這正是這類演算法能做到 O(n) 的原因。

KMP 與 AC 自動機都是這個視角的特例#

KMP 的 failure function（部分匹配表）描述的就是「在某個狀態讀到不匹配的字元時，該退回哪個狀態繼續嘗試」，而不必把主串指標往回拉。AC 自動機 則更進一步，把多個模式串疊在同一台 DFA 上，一次掃描就能同時找出所有模式串。

一旦理解「字串匹配 = 在 DFA 上跑狀態轉移」這個觀點，就能把 KMP、AC 自動機、甚至正則表達式引擎串成一條線——它們都是「先把模式編譯成狀態機，再用輸入驅動轉移」。帶著這個視角去讀 BM 與 KMP，failure function 會從「一張背不起來的表」變成「狀態機的轉移規則」。