LeetCode 28 Implement strStr() - 子串查找（KMP/內置函數）

題目翻譯

實現 strStr()：在 haystack 中找到 needle 首次出現的起始索引，不存在返回 -1。若 needle 為空串，返回 0（C/C++ 行為）。

解法一：暴力匹配（面試基礎版）

雙重循環，外層枚舉 haystack 起始位置，內層逐字符比對。最壞 O(m×n)，但在隨機字符串上較快。代碼簡潔，適合先寫出基本邏輯。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if (n == 0) return 0;
        for (int i = 0; i <= m - n; ++i) {
            int j = 0;
            for (; j < n; ++j)
                if (haystack[i + j] != needle[j]) break;
            if (j == n) return i;
        }
        return -1;
    }
};

解法二：KMP 算法（線性時間）

預處理 needle 計算 next 數組（最長公共前後綴長度），匹配失敗時利用 next 跳過已知匹配部分。時間 O(m+n)，空間 O(n)。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if (n == 0) return 0;
        vector next(n, 0);
        // 構建 next 數組
        for (int i = 1, j = 0; i < n; ++i) {
            while (j > 0 && needle[i] != needle[j]) j = next[j - 1];
            if (needle[i] == needle[j]) ++j;
            next[i] = j;
        }
        // 匹配
        for (int i = 0, j = 0; i < m; ++i) {
            while (j > 0 && haystack[i] != needle[j]) j = next[j - 1];
            if (haystack[i] == needle[j]) ++j;
            if (j == n) return i - n + 1;
        }
        return -1;
    }
};

解法三：調用庫函數（工程實踐）

C++ string::find、Java String.indexOf、Python str.find 皆已高度優化（通常採用 Two-Way 或 Boyer-Moore 變體），實際開發中直接調用最可靠。

class Solution {
public:
    int strStr(string haystack, string needle) {
        size_t pos = haystack.find(needle);
        return pos == string::npos ? -1 : (int)pos;
    }
};

複雜度對比

總結

面試中建議：先寫暴力版確保基本功，再手寫 KMP 展示算法深度，最後說明實際項目會直接用 string::find。注意 needle 為空串的邊界處理（返回 0）。