LeetCode 28 Implement strStr()：子串查找朴素實現

題目描述

實現 strStr()：返回 needle 在 haystack 中首次出現的下標，不存在返回 -1。若 needle 為空返回 0。

朴素算法 (Brute Force)

雙重循環：外層枚舉 haystack 起始位置 i，內層比對 needle 每個字符。時間 O((n-m+1)m)，對短模式串足夠。

參考代碼 (C)

bool isSub(char *str, char *sub) {
    int len = strlen(sub);
    for (int i = 0; i < len; ++i)
        if (str[i] != sub[i]) return false;
    return true;
}

int strStr(char *haystack, char *needle) {
    int hlen = strlen(haystack), nlen = strlen(needle);
    if (hlen == nlen && isSub(haystack, needle)) return 0;
    for (int i = 0; i <= hlen - nlen; ++i)
        if (isSub(haystack + i, needle)) return i;
    return -1;
}

進階算法提示

• KMP：預處理 next 數組，O(n+m)。
• Boyer-Moore / Sunday：實踐中更快。
• C++ 可直接用 string::find。