您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

字串查找演算法進階：從暴力優化到 KMP 核心思想

編輯：關於C

回顧：暴力查找與首輪優化

上篇實作的 strstr 採用雙層迴圈，外層遍歷主串 s 起始位置，內層比對模式串 p。第一版在 while 條件中反覆呼叫 strlen(s)，導致時間複雜度退化為 O(n²) 甚至 O(n³)。

優化一：預計算長度，避免重複掃描


char* strstr_v1(const char *s, const char *p) {
    if (!s || !p) return NULL;
    size_t n = strlen(s), m = strlen(p);
    if (m == 0) return (char*)s;
    if (n < m) return NULL;

    for (size_t i = 0; i <= n - m; ++i) {
        size_t j = 0;
        for (; j < m; ++j) if (s[i+j] != p[j]) break;
        if (j == m) return (char*)(s + i);
    }
    return NULL;
}

一次性計算 n, m，外層上界固定為 n-m，消除重複 strlen。但最壞情況（如 s="aaaa...ab", p="aaab"）仍為 O(n·m)。

優化二：利用已比對資訊跳過無效位置

觀察失配時刻：若 s[i..i+j-1] == p[0..j-1] 但 s[i+j] != p[j]，暴力演算法下一輪從 i+1 開始。但我們已知 s[i+1..i+j-1] == p[1..j-1]。若 p[1..j-1] 的前綴同時也是後綴，下一輪可直接從對應位置繼續比對，而非回退到 i+1。這正是 KMP 的核心洞見。

KMP 演算法核心：前綴表

定義

對模式串 p[0..m-1]，構建 next[m] 陣列（又稱 lps / failure function）：

next[i] = p[0..i] 最長真前綴同時也是真後綴的長度。

「真」意指不包含字串自身。例如 p = "ababac"：

i	p[i]	子串 p[0..i]	next[i]
0	a	a	0
1	b	ab	0
2	a	aba	1 (a)
3	b	abab	2 (ab)
4	a	ababa	3 (aba)
5	c	ababac	0

構建 `next` 陣列（O(m)）


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

KMP 查找主流程（O(n+m)）


char* kmp_search(const char *s, const char *p) {
    if (!s || !p) return NULL;
    int n = strlen(s), m = strlen(p);
    if (m == 0) return (char*)s;
    if (n < m) return NULL;

    int *next = malloc(m * sizeof(int));
    build_next(p, next, m);

    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) j = next[j-1];
        if (s[i] == p[j]) ++j;
        if (j == m) {
            free(next);
            return (char*)(s + i - m + 1);
        }
    }
    free(next);
    return NULL;
}

關鍵點解析

主串指標 i 從不回退：只單向掃描，保證 O(n)。
模式串指標 j 依 next 回退：利用已比對的前綴=後綴特性，跳過注定失敗的對齊位置。
next[0] = 0 慣例：失配於第一字元時，j 歸 0，主串繼續前進。
空模式串：習慣返回主串起始位址。

進階：`nextval` 優化（可選）

若 p[j] == p[next[j]]，失配後跳轉到 next[j] 仍會再次失配。可預計算 nextval 直接跳過：


void build_nextval(const char *p, int *nextval, int m) {
    int *next = malloc(m * sizeof(int));
    build_next(p, next, m);
    nextval[0] = 0;
    for (int i = 1; i < m; ++i) {
        if (p[i] == p[next[i]]) nextval[i] = nextval[next[i]];
        else nextval[i] = next[i];
    }
    free(next);
}

實務上現代 CPU 分支預測極強，next 與 nextval 差異微小，除非極度敏感場景否則標準 next 足矣。

工程落地建議

標準庫優先：生產碼直接用 strstr / memmem / std::string::find，編譯器/庫已高度優化（SIMD、Two-Way 演算法）。
KMP 適用場景：串流查找（無法隨機存取）、嵌入式無標準庫、教學展示、需自定義比較函數（如大小寫不敏感）。
多模式查找：需同時找多個模式串，改用 Aho-Corasick 自動機（Trie + failure links）。
測試矩陣：空串、單字元、重複字元、周期性模式、主串遠大於模式、Unicode 多位元組編碼。