C 語言實作子字串查找：朴素演算法完整解析

函式規格

// 回傳 substr 在 str 中首次出現的索引（0-based），找不到回傳 -1
int findstr(const char *str, const char *substr);

完整實作

int findstr(const char *str, const char *substr) {
    if (str == NULL || substr == NULL) return -1;

    size_t str_len = strlen(str);
    size_t sub_len = strlen(substr);

    if (sub_len > str_len) return -1;
    if (sub_len == 0) return 0; // 空字串視為在開頭找到

    // 動態配置暫存緩衝區（+1 留給結束符）
    char *tmp = (char*)malloc(sub_len + 1);
    if (!tmp) return -1; // 配置失敗

    for (size_t i = 0; i <= str_len - sub_len; ++i) {
        // 複製長度為 sub_len 的子串
        strncpy(tmp, str + i, sub_len);
        tmp[sub_len] = '\0'; // 確保結尾

        if (strcmp(tmp, substr) == 0) {
            free(tmp);
            return (int)i;
        }
    }

    free(tmp);
    return -1;
}

關鍵點解析

1. 防禦性檢查：空指標、長度邊界、空子串情況。
2. 暫存緩衝區：每次迴圈複製子串並補 \0，以便 strcmp 比較。也可用 memcmp 避免複製：
   if (memcmp(str + i, substr, sub_len) == 0) return i;
3. 記憶體管理：malloc/free 成對出現，所有返回路徑釋放資源。
4. 時間複雜度：O(n×m)，n=主串長、m=子串長。大數據量建議 KMP、BM 或 Sunday 演算法。

測試範例

int main() {
    printf("%d\n", findstr("hello world", "world")); // 6
    printf("%d\n", findstr("abcde", "f"));         // -1
    printf("%d\n", findstr("aaaaa", "aa"));        // 0
    printf("%d\n", findstr("", "a"));              // -1
    printf("%d\n", findstr("abc", ""));            // 0
    return 0;
}

進階優化方向

• 移除 malloc：若子串長度固定或較小，改用堆疊陣列 char tmp[256]。
• 改用 memcmp：避免 strncpy+strcmp 雙重掃描。
• 實作 KMP（O(n+m)）：預處理 next 陣列，避免回溯主串指標。

此實作適合教學、小規模文字處理；生產環境高效能需求請採用標準庫 strstr 或成熟演算法庫。