C語言手寫 strstr 子字串查找：雙指針匹配與回溯邏輯

標準語義

在 haystack 中找 needle 首次出現位置，找到返回指針，否則 NULL。

手寫實作 (暴力匹配 O(n*m))

#include 
char *my_strstr(const char *haystack, const char *needle) {
    assert(haystack && needle);
    if (!*needle) return (char*)haystack; // 空針返回 haystack
    
    for (const char *h = haystack; *h; h++) {
        const char *p1 = h;
        const char *p2 = needle;
        while (*p1 && *p2 && *p1 == *p2) {
            p1++; p2++;
        }
        if (!*p2) return (char*)h; // 完全匹配
    }
    return NULL;
}

關鍵邏輯

1. 外層遍歷 haystack 每個起始位置 h。
2. 內層雙指針 p1 (haystack), p2 (needle) 同步比對。
3. p2 走到 \0 → 完全匹配，返回 h。
4. 否則外層繼續下一個 h。

進階：KMP 算法 O(n+m)

預處理 needle 產生 next[] (部分匹配表)，失配時 p2 跳轉而非回溯 h，避免重複比較。標準庫通常實作 KMP 或 Two-Way 算法。

測試

int main() {
    char *s1 = "abbbcdef";
    char *s2 = "bbcd";
    printf("%s\n", my_strstr(s1, s2)); // bbcd
    return 0;
}