C語言手寫 strstr：子串查找算法實現與邊界處理

C語言手寫 strstr：子串查找算法實現與邊界處理

strstr 在主串中查找子串首次出現位置。本文實現朴素匹配算法，分析邊界條件與常見錯誤。

算法邏輯

1. 主串每個位置作為潛在起點
2. 依次比對子串字符
3. 全匹配返回起點指針
4. 失敗主串指針後移一位繼續
5. 遍歷結束返回 NULL

修正後的完整實現

#include <stdio.h>
#include <assert.h>

char *my_strstr(const char *haystack, const char *needle) {
    assert(haystack && needle);
    
    if (*needle == '\0') return (char *)haystack;  // 空子串匹配開頭
    
    const char *h = haystack;
    while (*h) {
        const char *h_start = h;
        const char *n = needle;
        
        while (*h && *n && *h == *n) {
            h++;
            n++;
        }
        
        if (*n == '\0') {
            return (char *)h_start;  // 找到，返回起點
        }
        
        h = h_start + 1;  // 回溯到下一個起始位置
    }
    
    return NULL;  // 未找到
}

int main() {
    char *s1 = "abbbcdef";
    char *s2 = "bbcd";
    char *ret = my_strstr(s1, s2);
    printf("結果：%s\n", ret ? ret : "NULL");
    return 0;
}

關鍵修正點（原代碼錯誤）

• 原代碼 s = p; 未聲明 s，且 q 未初始化
• 內層循環需保存 h_start 作為潛在匹配起點
• 匹配失敗時必須 h = h_start + 1 而非 h++（避免跳過字符）
• 空子串語義：標準返回主串開頭

測試用例

進階：KMP 算法預覽

朴素算法最壞 O(mn)，KMP 通過預處理 next 數組達到 O(m+n)。面試常考，建議掌握。