LeetCode Implement strStr() 超時分析：暴力匹配 O(mn) 在極端測例下 TLE，需 KMP/Boyer-Moore

你的暴力解法複雜度

int strStr(char *haystack, char *needle) {
    // 外層循環 m 次 (haystack 長度)
    // 內層 while 最多 n 次 (needle 長度)
    // 總時間 O(m * n)
}

LeetCode 測例包含極端情況：haystack = "aaaa...aaaa" (10^5), needle = "aaaa...aaab" (10^5) → 每次內層匹配到最後一個字符失敗，**實際操作次數 ≈ 10^10**，遠超 1-2 秒限制。

優化方案對比

KMP 核心代碼 (C++)

vector buildLPS(const string& pat) {
    int n = pat.size();
    vector lps(n, 0);
    for (int i = 1, len = 0; i < n; ) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;
    auto lps = buildLPS(needle);
    for (int i = 0, j = 0; i < haystack.size(); ) {
        if (haystack[i] == needle[j]) { ++i; ++j; }
        else if (j) j = lps[j - 1];
        else ++i;
        if (j == needle.size()) return i - j;
    }
    return -1;
}

為什麼本地運行正常而 OJ TLE？

• 本地測試數據量小、無極端構造。
• OJ 編譯優化等級 (O2) 一致，但**測例設計專門針對暴力匹配最壞情況**。
• 時間限制通常 1-2 秒，C++ 10^8 操作約 1 秒，10^10 必超時。

調試建議

1. 在本地構造極端測例：string(100000, 'a') + string(99999, 'a') + 'b'。
2. 使用 chrono 計時驗證優化前後差異。
3. LeetCode 支持 C++17，可直接用 haystack.find(needle) (內建優化) 通過，但面試需手寫 KMP。