C 語言 strstr 子字串搜尋：標準庫行為、三種手寫實現與邊界情況完整分析

strstr 在 <string.h> 中宣告：char* strstr(const char* haystack, const char* needle)。回傳 needle 在 haystack 首次出現位址，找不到回傳 NULL。needle 為空串時回傳 haystack。

標準庫行為關鍵點

• 不包含 needle 結尾 \0 的比對
• 大小寫敏感
• 時間複雜度 O(n*m)（朴素演算法），標準庫常優化為 Two-Way / Boyer-Moore

實現一：雙重迴圈 + 提前結束（教科書版）

char* my_strstr(char* s1, char* s2) {
    if (!*s2) return s1; // 空 needle
    while (*s1) {
        int n = 0;
        for (; *(s1+n) == *(s2+n); n++) {
            if (!*(s2+n+1)) return s1; // 完全匹配
        }
        s1++;
    }
    return NULL;
}

實現二：指標追蹤版（K&R 風格）

char* strstr(char* buf, char* sub) {
    if (!*sub) return buf;
    while (*buf) {
        char* bp = buf;
        char* sp = sub;
        do {
            if (!*sp) return buf;
        } while (*bp++ == *sp++);
        buf++;
    }
    return NULL;
}

實現三：現代 C++ 風格（const 正確、邊界檢查）

const char* isSub(const char* str, const char* sub) {
    if (!*sub) return str;
    for (const char* s = str; *s; s++) {
        const char* s1 = s;
        const char* s2 = sub;
        while (*s1 && *s2 && *s1 == *s2) { s1++; s2++; }
        if (!*s2) return s; // sub 走完 = 找到
    }
    return NULL;
}

邊界測試案例

效能提示

• 長字串/頻繁搜尋：考慮 strstr 標準庫（通常已優化）或 KMP/BM 演算法
• 需大小寫不敏感：自行實現 strcasestr（POSIX 擴展）或轉大小寫後搜尋
• C++ 專案優先用 std::string::find 或 std::search