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

字串查找演算法基礎：暴力比對法原理與 C 語言實作

編輯：關於C

問題定義

給定主串 haystack（長度 n）與模式串 needle（長度 m），找出 needle 在 haystack 中首次出現的起始位址；若不存在返回 NULL。這是 C 標準庫 strstr 的核心功能。

暴力比對法（Brute Force）邏輯

邊界檢查：任一指標為 NULL 直接返回 NULL。
長度預檢：若 n < m 必無解。
滑動窗口：主串起始位置 i 從 0 掃描至 n-m。
逐字元比對：對每個 i，檢查 haystack[i+j] == needle[j] 對所有 j ∈ [0, m) 是否成立。
提前剪枝：任一字元失配，立即中斷內層迴圈，嘗試下一個 i。
成功返回：內層迴圈完整跑完（j == m），返回 haystack + i。
遍歷結束：無匹配，返回 NULL。

C 語言標準實作


#include 
#include 

char* strstr_bruteforce(const char *haystack, const char *needle) {
    if (!haystack || !needle) return NULL;

    size_t n = strlen(haystack);
    size_t m = strlen(needle);

    if (m == 0) return (char*)haystack;  // 空模式串匹配開頭
    if (n < m) return NULL;

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

複雜度分析

指標	數值	說明
最好時間	O(m)	首位即匹配，或首字元即失配且模式串極短
最壞時間	O(n·m)	如 `haystack="aaaa...a"`, `needle="aaa...ab"`，每次比對 `m-1` 字元後失配
平均時間	O(n+m)	隨機字串下期望線性
空間複雜度	O(1)	僅常數額外變數

常見錯誤與修正

錯誤代碼	問題	修正
`while(*s && strlen(s) >= m)`	每輪呼叫 `strlen` 導致 O(n²)	預先計算 `n, m`，迴圈上界固定
`if (NULL == str \|\| NULL == str)`	重複檢查 `str`，漏檢 `data`	`if (!haystack \|\| !needle)`
未處理 `m == 0`	標準規定空模式串匹配開頭	開頭判斷 `if (m == 0) return (char*)haystack;`
外層上界寫 `i < n`	越界讀取 `haystack[i+j]`	`i <= n - m`（注意 size_t 無號減法下溢）

測試用例


#include 

void test_strstr(void) {
    assert(strstr_bruteforce(NULL, "abc") == NULL);
    assert(strstr_bruteforce("abc", NULL) == NULL);
    assert(strstr_bruteforce("", "abc") == NULL);
    assert(strstr_bruteforce("abc", "") == (char*)"abc");
    assert(strstr_bruteforce("hello world", "world") == (char*)"hello world" + 6);
    assert(strstr_bruteforce("aaaaa", "aa") == (char*)"aaaaa");
    assert(strstr_bruteforce("abc", "abcd") == NULL);
    assert(strstr_bruteforce("mississippi", "issip") == (char*)"mississippi" + 4);
}

優化方向預告

暴力法在最壞情況下效能不可接受。下一步優化思路：

預計算長度（已完成，消除重複 strlen）。
僅檢查必要長度：比對失配時，若剩餘主串長度 < 模式串長度，直接結束。
KMP 演算法：利用模式串內部結構（前綴=後綴），實現主串指標不回退，保證 O(n+m) 最壯複雜度。
Boyer-Moore / Sunday：從模式串尾部比對，配合壞字符/好後綴規則大幅跳躍，實務上常快於 KMP。
Two-Way / SIMD：現代標準庫（glibc, musl, MSVC）採用的混合策略，利用 CPU 向量指令並行比對。

總結

暴力比對法雖簡單，但包含「邊界處理、雙層迴圈、提前剪枝、指標運算」等系統程式設計核心技能。熟練寫出無 Bug 版本，是進階學習 KMP、BM、AC 自動機等高階字串演算法的基石。工程上：除非極度受限環境，否則優先使用標準庫 strstr；面試中：能手寫正確暴力版、說清複雜度、指出優化方向即達標。