萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C 語言 strstr 子串查找函數原理與多種手寫實現完整解析

標準庫原型與語義


#include 
char *strstr(const char *haystack, const char *needle);
// 在 haystack 中查找 needle 首次出現位置
// 返回:指向匹配起始位置的指針;未找到返回 NULL
// 特殊情況:needle 為空串 "" 時返回 haystack

核心算法:朴素模式匹配(Brute Force)

時間複雜度 O(n*m),n=haystack 長度,m=needle 長度。對於短模式串極其高效,且代碼簡潔,是教學與嵌入式首選。

三種手寫實現風格對比

實現一:雙層循環 + 索引偏移(教科書風格)


char *my_strstr(const char *s1, const char *s2) {
    if (!*s2) return (char*)s1;          // 空模式串
    for (; *s1; ++s1) {                  // 遍歷主串每個起始位置
        int n = 0;
        while (s1[n] == s2[n]) {         // 逐字符比對
            if (!s2[n+1]) return (char*)s1; // 模式串到達末尾 → 匹配成功
            ++n;
        }
    }
    return NULL;
}

實現二:雙指針推進(K&R 風格,緊湊)


char *strstr(const char *buf, const char *sub) {
    if (!*sub) return (char*)buf;
    for (; *buf; ++buf) {
        const char *bp = buf, *sp = sub;
        do {
            if (!*sp) return (char*)buf; // sp 走到末尾
        } while (*bp++ == *sp++);
    }
    return NULL;
}

精妙點:do-while 保證至少比較一次;*bp++ == *sp++ 同時完成比較與推進。

實現三:現代 C++ 風格(const 正確、邊界檢查)


const char *isSub(const char *str, const char *subs) {
    if (!*subs) return str;
    for (const char *tmp = str; *tmp; ++tmp) {
        const char *t1 = tmp, *s1 = subs;
        while (*s1 && *t1 && *s1 == *t1) { ++s1; ++t1; }
        if (!*s1) return tmp;            // 子串完全匹配
    }
    return nullptr;
}

進階算法:KMP / Boyer-Moore / Sunday

當 needle 較長(> 100 字符)或在海量文本中高頻查找時,朴素算法效率不足。標準庫實現(glibc、musl、MSVC STL)通常採用Two-Way 算法或Boyer-Moore-Horspool變體,最壞情況 O(n+m),平均極快。

性能基準建議

場景推薦方案
短模式串(< 30 字符)、低頻調用標準庫 strstr / 朴素手寫
長模式串、高頻/海量文本標準庫(已優化)或顯式 KMP/BMH
嵌入式無標準庫朴素雙指針版(代碼最小)
C++ 代碼庫std::string::find / std::search (KMP 可選)

常見坑點

  1. 空模式串:strstr(s, "") == s,手寫必須處理。
  2. const 正確性:參數與返回值均為 const char*,避免誤修改字面量。
  3. 重疊查找:strstr("aaa", "aa") 返回首個 "aa",若需所有位置需自行循環調用。
  4. 編碼假設:標準 strstr 按字節比較,UTF-8 多字節字符下仍正確(因無字節序歧義),但不支持「字符級」語義查找。

結語

strstr 看似簡單,實則蘊含經典字符串匹配算法演進史。日常開發直接信任標準庫實現;面試/教學/極簡環境時,掌握雙指針推進版即可兼顧可讀性與正確性。若遇性能瓶頸,優先考慮升級算法而非微優化朴素代碼。

copyright © 萬盛學電腦網 all rights reserved