LeetCode 28. 實現 strStr()：暴力匹配與 KMP 算法 C 語言解法

編輯：關於C語言

LeetCode 28. 實現 strStr()：暴力匹配與 KMP 算法 C 語言解法

實現 `strStr(haystack, needle)`：返回 `needle` 在 `haystack` 首次出現的索引，不存在返回 -1。本文提供**暴力匹配 O(mn)** 基礎解與 **KMP O(m+n)** 進階解，詳細講解 `next` 數組構建與匹配流程。

暴力匹配法（直觀易寫，面試兜底）

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack);
    int m = strlen(needle);
    if (m == 0) return 0; // 空串匹配索引0

    for (int i = 0; i <= n - m; i++) {       // 主串起始位置
        int j;
        for (j = 0; j < m; j++) {            // 模式串逐字符比較
            if (haystack[i+j] != needle[j]) break;
        }
        if (j == m) return i; // 完全匹配
    }
    return -1;
}

時間 O((n-m+1)·m) ≈ O(mn)，空間 O(1)。短文本/面試無 KMP 要求時足夠。

KMP 算法核心：next 數組（最長公共前後綴）

`next[j]` 表示模式串 `needle[0..j-1]` 的**最長真前綴同時也是真後綴的長度**。匹配失敗時，模式串右移 `j - next[j]` 位，避免主串指針回溯。

next 數組構建（標準版）

void build_next(const char* pat, int* next, int m) {
    next[0] = -1; // 約定：next[0] = -1 便於統一邏輯
    int k = -1;
    for (int j = 1; j < m; j++) {
        while (k >= 0 && pat[k+1] != pat[j]) k = next[k];
        if (pat[k+1] == pat[j]) k++;
        next[j] = k;
    }
}

示例：`pat = "ABABC"` → `next = [-1, 0, 0, 1, 2]`。
含義：`j=4` (字符 `C`) 失敗時，`k=next[4]=2`，模式串右移 `4-2=2` 位，`pat[2]='A'` 繼續匹配。

KMP 匹配主流程

int strStr_kmp(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0) return 0;
    int *next = malloc(m * sizeof(int));
    build_next(needle, next, m);

    int i = 0, j = 0; // i: 主串索引, j: 模式串索引
    while (i < n) {
        if (j == -1 || haystack[i] == needle[j]) {
            i++; j++; // 匹配或 j==-1 重置
        } else {
            j = next[j]; // 失敗跳轉
        }
        if (j == m) { // 完全匹配
            free(next);
            return i - m;
        }
    }
    free(next);
    return -1;
}

關鍵點總結

next[0] = -1 統一了「失敗跳轉」與「首字符匹配」邏輯：`j=-1` 時強制 `i++, j++` 相當於模式串右移 1 位重新匹配首字符。
主串指針 `i` 永不回溯：這是 KMP 線性時間的根本原因。
空模式串返回 0：符合 C 標準庫 `strstr` 行為及 LeetCode 定義。
內存管理：`next` 數組動態分配，匹配結束/返回前必須 `free`。

複雜度對比

算法	時間	空間	適用場景
暴力匹配	O(mn)	O(1)	短文本、面試兜底、模式串極短
KMP	O(m+n)	O(m)	長文本、高頻查詢、模式串較長
Boyer-Moore	O(m+n) 平均	O(σ)	實際最快（grep等），實現複雜
Sunday	O(m+n) 平均	O(σ)	工程常用，代碼較簡潔

測試用例

haystack = "hello", needle = "ll"  → 2
haystack = "aaaaa", needle = "bba" → -1
haystack = "", needle = ""         → 0
haystack = "abc", needle = ""      → 0
haystack = "mississippi", needle = "issip" → 4