C語言字符串查找函數深度解析：strstr手寫實現邏輯詳解

代碼功能概覽

本文詳細解析一個手寫的字符串查找函數 fun(char *s, char *t)，其功能等同於標準庫 strstr：在主字符串 s 中查找子字符串 t 首次出現的位置，若找到返回該位置指針，否則返回 NULL。

完整代碼與逐行註釋

#include <stdio.h>
#include <string.h>

char *fun(char *s, char *t) {
    char *p, *r, *a;      // p:遍歷主串臨時指針 r:遍歷子串臨時指針 a:記錄匹配起始位置
    a = NULL;             // 初始化未找到
    
    while (*s) {          // 外層循環：遍歷主串每個字符作為潛在起點
        p = s;            // p 指向主串當前嘗試起點
        r = t;            // r 指向子串首字符
        
        while (*r) {      // 內層循環：逐字符比較主串與子串
            if (*r == *p) {  // 字符匹配
                r++;         // 子串指針後移
                p++;         // 主串指針後移
            } else {
                break;       // 失配，跳出內層循環
            }
        }
        
        if (*r == '\0')   // 內層循環正常結束(子串遍歷完)，說明完全匹配
            a = s;        // 記錄匹配起始位置(當前主串指針s)
        
        s++;              // 主串指針後移，嘗試下一個起點
    }
    return a;             // 返回首次匹配位置或 NULL
}

int main(void) {
    char s[100], t[100], *p;
    printf("Please enter string S: ");
    scanf("%s", s);
    printf("Please enter substring t: ");
    scanf("%s", t);
    p = fun(s, t);
    if (p)
        printf("The result is: %s\n", p);  // 輸出從匹配位置開始的後綴
    else
        printf("Not found!\n");
    return 0;
}

核心邏輯圖解

雙指針匹配機制

外層指針 s：掃描主串每個位置作為「候選起點」。
內層指針 p, r：p 從候選起點開始，r 從子串開頭開始，同步前進比較。

關鍵判斷點

• if (*r == *p)：字符匹配，雙指針推進。
• else break：失配，立即終止本輪嘗試。
• if (*r == '\0')：子串 r 走到末尾，說明從 s 開始的子串完全匹配，記錄 a = s。

執行流程實例演示

案例 1：成功匹配

s = "Student", t = "Stu"

1. s 指向 'S'，p='S', r='S' → 匹配，推進
2. p='t', r='t' → 匹配，推進
3. p='u', r='u' → 匹配，推進
4. r 指向 '\0'，內層結束，*r == '\0' 為真，a = s (指向 "Student" 首地址)
5. 返回 a，主函數輸出 "Student"

案例 2：匹配失敗

s = "Student", t = "abc"

1. s='S', r='a' → 失配，break
2. s='t', r='a' → 失配，break
3. ... 遍歷完主串 a 仍為 NULL
4. 返回 NULL，主函數輸出 "Not found!"

常見問題釐清

Q: 代碼中 r 最後為什麼等於 '\0'？

A: r 是指向子串的指針。內層循環條件是 while (*r)，當 r 指向字符串結束符 '\0' 時，*r 為 0 (假)，循環終止。此時 r 指向的正是 '\0'，所以 *r == '\0' 成立，標誌著子串所有字符均已匹配完畢。

Q: 為什麼返回 a 而不是 p？

A: p 在匹配過程中不斷後移，最終指向主串匹配段的下一個字符；而 s (賦值給 a) 保持指向匹配的起始位置，這正是 strstr 的語義要求。

算法複雜度與改進方向

• 時間複雜度：最壞 O(m×n) (m,n 為主/子串長度)，如主串 "aaaaaab" 找 "aaab"。
• 空間複雜度：O(1)，僅用常數額外空間。
• 優化方向：KMP 算法 (O(m+n))、Boyer-Moore 算法、Sunday 算法等，通過預處理子串跳過不必要的比較。

總結

這段代碼雖屬暴力匹配，但邏輯清晰，完美演示了雙指針同步遍歷、狀態保存與恢復的核心思想，是理解字符串匹配算法的優秀入門教材。實際工程中應優先使用標準庫 strstr (通常已優化)，但在嵌入式環境或面試手寫算法時，掌握此邏輯至關重要。