現場手寫字符串庫函數：strstr、strcpy、strpbrk 完全攻略

背景：為什麼面試要手寫庫函數？

中小公司資源有限，除抄襲大廠題庫，常考察基礎功底與細節把控：限時 10 分鐘實現 strcpy/strcat/strstr 等。這不僅是語法測試，更是對邊界條件、指針運算、內存安全、const 正確性的綜合考驗。

1. 字符串查找：strstr 實現

朴素 O(nm) 版

// 返回首次出現位置（1-based），未找到返回 -1
int my_strstr(const char *haystack, const char *needle) {
    if (!haystack || !needle) return -1;
    int n = strlen(haystack), m = strlen(needle);
    if (n < m) return -1;

    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        for (; j < m; ++j)
            if (haystack[i + j] != needle[j]) break;
        if (j == m) return i + 1; // 1-based 索引
    }
    return -1;
}

進階：KMP O(n+m)

預處理 `next` 數組（最長公共前後綴），失配時跳過已知匹配前綴。面試可口述原理，關鍵代碼：

void build_next(const char *p, int *next, int m) {
    next[0] = -1;
    for (int i = 1, j = -1; i < m; ++i) {
        while (j >= 0 && p[j + 1] != p[i]) j = next[j];
        if (p[j + 1] == p[i]) ++j;
        next[i] = j;
    }
}

2. 字符串拷貝：strcpy 進階實現

面試評分標準（滿分 10）：

滿分版本

char *my_strcpy(char *dest, const char *src) {
    assert(dest != NULL && src != NULL);
    char *ret = dest;
    // 注意：標準 strcpy 不處理重疊，重疊行為未定義
    while ((*dest++ = *src++) != '\0');
    return ret;
}

3. 字符集查找：strpbrk 實現

查找字符串中首個出現在字符集 accept 中的字符。

char *my_strpbrk(const char *s, const char *accept) {
    assert(s && accept);
    bool table[256] = {false};
    for (const char *p = accept; *p; ++p) table[(unsigned char)*p] = true;
    for (; *s; ++s) if (table[(unsigned char)*s]) return (char *)s;
    return NULL;
}

位圖法 O(n+m)，工程中極其常用（如 strspn/strcspn 同理）。

4. 找首個不重複字符

char firstUniqueChar(const char *s) {
    int cnt[256] = {0};
    for (const char *p = s; *p; ++p) cnt[(unsigned char)*p]++;
    for (const char *p = s; *p; ++p) if (cnt[(unsigned char)*p] == 1) return *p;
    return '\0'; // 無唯一字符
}

面試加分項總結

1. const 正確性：輸入指針加 const
2. 空指針斷言：assert 或 返回錯誤碼
3. 返回值設計：鏈式調用需返回 dest
4. 重疊語義說明：區分 strcpy (UB) 與 memmove (安全)
5. 邊界測試用例：空串、單字符、重疊、超長
6. 複雜度分析：主動說明時間/空間

總結

手寫庫函數看似基礎，實則考察工程素養：細節決定成敗。掌握標準庫實現精髓，才能在造輪子時不踩坑，在用輪子時知其然更知其所以然。