字串搜尋演算法系列（上）：基本暴力比對法與效能優化初探

字串搜尋的三大主流方向

1. 基本暴力比對（Brute Force）：簡單直觀，最壞 O(M×N)。
2. KMP 演算法：預處理模式串，消除回溯，O(M+N)。
3. 多核平行搜尋：利用多核 CPU 切分文本並行匹配。

基本暴力比對法邏輯

文本串 `str`，模式串 `data`（長度 `len`）。

1. 外層迴圈：`str` 逐字元滑動（`str++`）。
2. 內層迴圈：比對 `str[i]` 與 `data[i]`，`i=0..len-1`。
3. 全匹配 → 返回當前 `str` 位址。
4. 任一失配 → `break` 內層，外層繼續下一字元。
5. 剩餘文本長度 < `len` → 提前結束。

初版實作（含效能隱憂）

char* my_strstr(const char* str, const char* data) {
    if (NULL == str || NULL == data) return NULL;

    int len = strlen(data);
    if (0 == len) return (char*)str; // 空模式串匹配開頭

    while (*str && strlen(str) >= (size_t)len) { // ⚠️ 每次迴圈呼叫 strlen(str)！
        int i;
        for (i = 0; i < len; ++i) {
            if (str[i] != data[i]) break;
        }
        if (i == len) return (char*)str; // 找到
        ++str;
    }
    return NULL;
}

效能瓶頸分析

`while` 條件中呼叫 `strlen(str)` 導致每次外層迴圈掃描剩餘字串長度。若文本長度 M 遠大於模式長度 N，總操作約 O(M²/2)，極度低效。

優化一：僅檢查前 N 字元是否合法

寫入 `check_length_of_str(str, len)`：只檢查 `str[0..len-1]` 是否含 `\0`，O(N) 替代 O(M)。

int check_length_of_str(const char* str, int len) {
    for (int i = 0; i < len; ++i)
        if ('\0' == str[i]) return 0;
    return 1;
}

char* my_strstr_v2(const char* str, const char* data) {
    if (NULL == str || NULL == data) return NULL;
    int len = strlen(data);
    if (0 == len) return (char*)str;

    while (*str && check_length_of_str(str, len)) { // O(N) 檢查
        int i;
        for (i = 0; i < len; ++i)
            if (str[i] != data[i]) break;
        if (i == len) return (char*)str;
        ++str;
    }
    return NULL;
}

優化二：利用上一輪比對資訊，避免任何長度檢查

觀察：外層迴圈每次 `str++`。若上一輪 `str[0..len-1]` 合法（無 `\0`），則本輪只需檢查 `str[len]` 是否為 `\0` 即可！

char* my_strstr_v3(const char* str, const char* data) {
    if (NULL == str || NULL == data) return NULL;

    int len = strlen(data);
    if (0 == len) return (char*)str;

    // 進入迴圈前，先檢查一次完整長度
    if (strlen(str) < (size_t)len) return NULL;

    while (*str) {
        int i;
        for (i = 0; i < len; ++i)
            if (str[i] != data[i]) break;

        if (i == len) return (char*)str; // 找到

        // 關鍵優化：只檢查新進窗口的最後一字元
        if ('\0' == str[len]) break; // 剩餘長度不足

        ++str;
    }
    return NULL;
}

測試案例

void test_strstr() {
    assert(NULL == my_strstr(NULL, "china"));
    assert(NULL == my_strstr("hello world", "china"));
    assert(NULL != my_strstr("hello china", "china"));
    assert(NULL != my_strstr("china", "china")); // 開頭匹配
    assert(NULL == my_strstr("abc", "abcd"));    // 模式比文本長
    printf("All tests passed.\n");
}

總結與展望

暴力法經優化後，對於短模式串、隨機文本已具實用效能。但最壞情況（如 `str="aaaaa...aab"`, `data="aaab"`）仍為 O(M×N)。下一篇將深入 **KMP 演算法**，從根本上消除回溯，達成 O(M+N) 理論下界。