#include
char *strstr(const char *haystack, const char *needle);
// 在 haystack 中查找 needle 首次出現位置
// 返回:指向匹配起始位置的指針;未找到返回 NULL
// 特殊情況:needle 為空串 "" 時返回 haystack
時間複雜度 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;
}
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++ 同時完成比較與推進。
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;
}
當 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 可選) |
strstr(s, "") == s,手寫必須處理。const char*,避免誤修改字面量。strstr("aaa", "aa") 返回首個 "aa",若需所有位置需自行循環調用。strstr 按字節比較,UTF-8 多字節字符下仍正確(因無字節序歧義),但不支持「字符級」語義查找。strstr 看似簡單,實則蘊含經典字符串匹配算法演進史。日常開發直接信任標準庫實現;面試/教學/極簡環境時,掌握雙指針推進版即可兼顧可讀性與正確性。若遇性能瓶頸,優先考慮升級算法而非微優化朴素代碼。