字串搜尋演算法系列（中）：長度檢查優化與 KMP 演算法核心思想

回顧：暴力法的根本缺陷

優化版暴力法雖減少 `strlen` 呼叫，但失配時仍將文本指標僅後移 1 位，導致已比對過的字元被重複檢查。

範例：

文本 A: b a a a a a b c d
模式 B:     a a a a b
           ↑ 失配於第 5 字元 (A[5]='a' vs B[4]='b')

暴力法下一步：A 後移 1 位，重新比對 B[0..3] 與 A[2..5] → 明明剛剛比對過相等！

KMP 核心洞見：利用「已匹配前綴」資訊

失配位置 `p`（0-based），表示 `B[0..p-1]` == `A[i..i+p-1]`。
下一步不必從 `B[0]` 開始，而是找 `B` 中最長真前綴同時也是真後綴的長度 `k`，使 `B[0..k-1]` == `B[p-k..p-1]`。
此時可直接從 `B[k]` 與 `A[i+p]` 繼續比對，文本指標 `i` 不回退。

部分匹配表（Next 陣列 / Failure Function）構建

對模式串 `B` 每個位置 `j`，計算 `next[j]` = 失配時模式串應跳轉的索引（即最長公共前後綴長度）。

計算邏輯（標準 O(N) 建表法）

void build_next_array(const char* pattern, int* next, int len) {
    next[0] = 0; // 或 -1 視實作風格
    int k = 0;   // 當前最長前綴長度

    for (int j = 1; j < len; ++j) {
        while (k > 0 && pattern[j] != pattern[k])
            k = next[k-1]; // 遞歸縮短前綴

        if (pattern[j] == pattern[k]) ++k;
        next[j] = k;
    }
}
// 範例 pattern "ABABC"
// j=0: A  next=0
// j=1: B  next=0
// j=2: A  next=1 (A)
// j=3: B  next=2 (AB)
// j=4: C  next=0

KMP 搜尋主流程

char* kmp_search(const char* text, const char* pattern) {
    int n = strlen(text), m = strlen(pattern);
    if (m == 0) return (char*)text;

    int* next = (int*)malloc(m * sizeof(int));
    build_next_array(pattern, next, m);

    int i = 0, j = 0; // i: text index, j: pattern index
    while (i < n) {
        while (j > 0 && text[i] != pattern[j])
            j = next[j-1]; // 模式串回退，文本指標 i 不動

        if (text[i] == pattern[j]) ++j;
        ++i;

        if (j == m) { // 完全匹配
            free(next);
            return (char*)(text + i - m);
        }
    }
    free(next);
    return NULL;
}

關鍵特性對比

原文程式碼風格的 KMP 實作解析

原文採用失配位移量表（`pData[index]` 表示失配時文本應前移多少位），邏輯等價但視角不同：

• `calculate_for_special_index`：對模式串每位置 `index`，暴力枚舉左移位數，找到最大合法位移。
• `calculate_for_max_positon`：預計算所有位置位移量。
• 搜尋時：`value = pData[index]; str += value;` 直接跳躍。

此法直觀但建表為 O(N²)，標準 Next 陣列法 O(N) 更優。

總結

KMP 之所以快，在於犧牲 O(N) 空間換取 O(M) 時間，核心是不讓文本指標回退。掌握 Next 陣列構建邏輯（`k` 變數追蹤最長前綴），即掌握 KMP 精髓。下篇將實作完整 KMP 並介紹多核平行搜尋。