`strstr` 在主串中查找子串首次出現位置。本文提供標準朴素實現、邊界處理、最壞情況分析、KMP/O(n+m) 優化路徑。
#includechar *my_strstr(const char *haystack, const char *needle) { assert(haystack && needle); if (*needle == '\0') return (char *)haystack; // 空子串 for (const char *h = haystack; *h; h++) { const char *p1 = h; const char *p2 = needle; while (*p1 && *p2 && *p1 == *p2) { p1++; p2++; } if (*p2 == '\0') return (char *)h; // 完全匹配 } return NULL; }
int main() {
struct { const char *haystack; const char *needle; const char *expected; } tests[] = {
{"abbbcdef", "bbcd", "bbcdef"},
{"hello world", "world", "world"},
{"aaaaa", "aa", "aaaaa"},
{"abc", "", "abc"},
{"", "a", NULL},
{"abc", "abcd", NULL},
{"mississippi", "issip", "issippi"},
};
for (size_t i = 0; i < sizeof(tests)/sizeof(tests[0]); i++) {
char *res = my_strstr(tests[i].haystack, tests[i].needle);
printf("strstr(\"%s\", \"%s\") = %s %s\n",
tests[i].haystack, tests[i].needle,
res ? res : "NULL",
(res == tests[i].expected || (res && tests[i].expected && strcmp(res, tests[i].expected)==0)) ? "✓" : "✗");
}
return 0;
}
strstr("abbbcdef", "bbcd") = bbcdef ✓
strstr("hello world", "world") = world ✓
strstr("aaaaa", "aa") = aaaaa ✓
strstr("abc", "") = abc ✓
strstr("", "a") = NULL ✓
strstr("abc", "abcd") = NULL ✓
strstr("mississippi", "issip") = issippi ✓
haystack: "aaaaa...aab" (n 個 a 後接 b) needle: "aaaaab" (m-1 個 a 後接 b) // 每次匹配失敗都在最後一個字元 // 比較次數 ≈ n × m // 例：n=10000, m=500 → 500萬次比較
// 計算 next 數組：next[i] = needle[0..i] 最長真前綴=真後綴長度
void compute_next(const char *needle, int *next, int m) {
next[0] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) j = next[j-1];
if (needle[i] == needle[j]) j++;
next[i] = j;
}
}
// KMP 查找：O(n+m)
char *kmp_strstr(const char *haystack, const char *needle) {
int n = strlen(haystack), m = strlen(needle);
if (m == 0) return (char*)haystack;
int *next = malloc(m * sizeof(int));
compute_next(needle, next, m);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) j = next[j-1];
if (haystack[i] == needle[j]) j++;
if (j == m) {
free(next);
return (char*)(haystack + i - m + 1);
}
}
free(next);
return NULL;
}
| 算法 | 時間 | 空間 | 特點 |
|---|---|---|---|
| 朴素 | O(n×m) | O(1) | 簡單，短模式串實際常更快 |
| KMP | O(n+m) | O(m) | 不回溯主串，流式處理友好 |
| Boyer-Moore | O(n/m) 平均 | O(σ) | 從右向左比較，跳躍大，實務最快 |
| Sunday | O(n/m) 平均 | O(σ) | BM 改進，看主串下一字元決定跳躍 |
| Rabin-Karp | O(n+m) 平均 | O(1) | 滾動哈希，多模式匹配優勢 |
| Two-Way | O(n+m) | O(1) | glibc 實際採用，無額外空間 |
`strstr` 朴素實現**簡單正確、短串高效**，但最壞 O(n×m)。生產環境 **glibc 使用 Two-Way 算法 (O(n+m), O(1) 空間)**，兼顧理論最優與實務效能。面試必會：朴素雙指針邏輯、空串處理、KMP next 數組構造、BM/Sunday 思想、標準庫實際採用算法。
