C語言手寫實現 strstr 子串查找函數

strstr 函數規範

char *strstr(const char *haystack, const char *needle)：在主串 `haystack` 中查找子串 `needle` 首次出現位置，返回該位置指針；未找到返回 `NULL`。

暴力匹配算法實現

#include <stdio.h>

const char *my_strstr(const char *str, const char *sub_str) {
    for (int i = 0; str[i] != '\0'; i++) {
        int start = i;          // 記錄當前嘗試的起始位置
        int j = 0;
        // 逐字符比對
        while (str[i] == sub_str[j] && sub_str[j] != '\0') {
            i++; j++;
        }
        if (sub_str[j] == '\0') {  // 子串完全匹配
            return &str[start];
        }
        i = start;  // 回溯：主串指針回到起始位置，外層 for 會 i++
    }
    return NULL;
}

int main() {
    char *s = "1233345hello";
    char *sub = "345";
    printf("%s\n", my_strstr(s, sub));  // 輸出: 345hello
    return 0;
}

算法邏輯圖解

主串: 1 2 3 3 3 4 5 h e l l o
           ↑         ↑
          i=2      找到 "345" 起始位置
子串:     3 4 5
          ↑ ↑ ↑
          j=0 1 2  匹配成功，返回 &str[2]

關鍵實現細節

1. 雙指針/雙索引：外層遍歷主串起始位置 `i`，內層比對子串 `j`
2. 回溯機制：`i = start` 確保下一輪從主串下一字符開始
3. 終止條件：`sub_str[j] == '\0'` 表示子串遍歷完畢 = 匹配成功
4. 邊界處理：主串提前結束（`str[i] == '\0'`）自動返回 `NULL`

時間複雜度分析

• 最壞 O(m×n)：如主串 `aaaaaab`，子串 `aaab`，大量回溯
• 平均 O(m+n)：隨機字符串下較快
• 空間 O(1)：無額外記憶體

優化方向：KMP 算法

暴力匹配的缺點是主串指針回溯。KMP 通過預處理子串構建next 數組（部分匹配表），實現主串指針不回溯，時間複雜度穩定 O(m+n)。

KMP 核心框架（僅供參考）

// 構建 next 數組
void build_next(const char *pat, int *next, int m) {
    next[0] = -1;
    int k = -1, j = 0;
    while (j < m - 1) {
        if (k == -1 || pat[j] == pat[k]) next[++j] = ++k;
        else k = next[k];
    }
}

// KMP 查找
const char *kmp_strstr(const char *txt, const char *pat) {
    int n = strlen(txt), m = strlen(pat);
    int *next = malloc(m * sizeof(int));
    build_next(pat, next, m);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || txt[i] == pat[j]) { i++; j++; }
        else j = next[j];
    }
    free(next);
    return (j == m) ? &txt[i - m] : NULL;
}

標準庫 vs 手寫對比

| 維度 | `strstr` (glibc) | 本文暴力版 | KMP 版 | |------|------------------|------------|--------| | 算法 | Two-Way / BMH 混合 | 暴力回溯 | KMP | | 最壞情況 | O(m+n) | O(m×n) | O(m+n) | | 適用場景 | 通用生產環境 | 教學、極短模式串 | 教學、長模式串 |

總結

本文實現了教學級的暴力模式匹配，代碼簡潔、邏輯清晰，適合理解「雙指針回溯」基本思想。工程生產環境請直接使用標準庫 `strstr`（高度優化、經過充分測試），或在特定場景（如嵌入式無標準庫）考慮 KMP 等線性算法。