一步步演算法：KMP 字串搜尋演算法深度解析與平行化改進

編輯：關於C語言

KMP（Knuth-Morris-Pratt）演算法以 O(n+m) 時間解決字串匹配問題，核心在於「失敗函數」（next 陣列）預計算模式串的自匹配信息，避免主串回溯。本文從原理推導到工程級實作，並探討 OpenMP 平行化策略。

核心洞見：為什麼不需要回溯主串？

當模式串 P 在位置 j 失配時，P[0..j-1] 已知與主串 S 對應段完全匹配。利用 P 內部的前綴/後綴重疊資訊，可直接決定 P 下一步應對齊 S 的哪個位置，主串指針 永不後退。

Next 陣列（失敗函數）構建

next[j] 定義：模式串前 j 個字元（0~j-1）中，最長真前綴同時也是後綴的長度。失配時模式串指針跳至 next[j]。

void build_next(const char *pat, int *next, int m) {
    next[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pat[i] != pat[j]) j = next[j-1];
        if (pat[i] == pat[j]) j++;
        next[i] = j;
    }
}

範例：P = "ABABC" → next = [0,0,1,2,0]

KMP 主搜尋流程

const char* kmp_search(const char *text, const char *pat) {
    int n = strlen(text), m = strlen(pat);
    if (m == 0) return text;
    
    int *next = (int*)malloc(m * sizeof(int));
    build_next(pat, next, m);
    
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pat[j]) j = next[j-1];
        if (text[i] == pat[j]) j++;
        if (j == m) {
            free(next);
            return text + i - m + 1;  // 找到匹配起始位置
        }
    }
    free(next);
    return NULL;
}

關鍵細節與優化

Next 陣列變體：標準版在連續相同字元時可優化為 nextval，進一步減少比較次數
邊界條件：空模式串、主串長度不足、多重匹配（找到後 j = next[j-1] 繼續）
記憶體安全：檢查 malloc 回傳值，使用 size_t 避免溢位

OpenMP 平行化策略（多核搜尋）

字串搜尋天然適合資料平行：將主串切分為重疊區塊，各執行緒獨立執行 KMP。

#include <omp.h>

const char* kmp_parallel(const char *text, const char *pat) {
    int n = strlen(text), m = strlen(pat);
    if (m == 0) return text;
    
    int *next = (int*)malloc(m * sizeof(int));
    build_next(pat, next, m);
    
    const char *result = NULL;
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        int num_threads = omp_get_num_threads();
        int chunk = (n + num_threads - 1) / num_threads;
        int start = tid * chunk;
        int end = (tid == num_threads - 1) ? n : start + chunk + m - 1;  // 重疊 m-1 字元
        if (end > n) end = n;
        
        for (int i = start, j = 0; i < end && !result; i++) {
            while (j > 0 && text[i] != pat[j]) j = next[j-1];
            if (text[i] == pat[j]) j++;
            if (j == m) {
                #pragma omp critical
                if (!result) result = text + i - m + 1;
            }
        }
    }
    free(next);
    return result;
}

關鍵點：區塊需重疊 m-1 字元，跨越邊界的匹配才不會遺漏。critical 區段確保首次找到即回傳。