LeetCode Implement strStr() 字符串匹配 KMP 與 Rabin-Karp

問題

實現 strStr(haystack, needle)：返回 needle 在 haystack 中首次出現的索引，不存在返回 -1。空 needle 返回 0。

方法一：暴力雙指針 O(MN)

對每個起始位置嘗試匹配，失敗則回退。LeetCode 測試數據會 TLE。

方法二：Rabin-Karp 滾動哈希 O(N+M)

核心思想

• 將字符串視為 B 進制數（B 取大於字符集大小的質數，如 131 或 29）
• 預計算 needle 哈希值 H_needle
• 滑動窗口維護 haystack 長度 M 子串哈希 H_win
• H_win = (H_win - haystack[i-M]*B^{M-1}) * B + haystack[i]
• 哈希相等時再驗證一次（防碰撞）

代碼實現

class Solution {
    static constexpr int BASE = 131;
    static constexpr long long MOD = 1e9+7; // 可選，防溢出

    int charVal(char c) { return c - 'a' + 1; } // 假設小寫字母

public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        if (m > n) return -1;

        long long hashN = 0, hashH = 0, power = 1;
        for (int i = 0; i < m; ++i) {
            hashN = (hashN * BASE + charVal(needle[i])) % MOD;
            hashH = (hashH * BASE + charVal(haystack[i])) % MOD;
            if (i < m-1) power = (power * BASE) % MOD;
        }

        if (hashH == hashN && haystack.substr(0, m) == needle) return 0;

        for (int i = m; i < n; ++i) {
            hashH = (hashH - charVal(haystack[i-m]) * power % MOD + MOD) % MOD;
            hashH = (hashH * BASE + charVal(haystack[i])) % MOD;
            if (hashH == hashN && haystack.substr(i-m+1, m) == needle)
                return i - m + 1;
        }
        return -1;
    }
};

方法三：KMP 算法 O(N+M) 確定性

前綴函數（next 數組/失敗函數）

next[i] = 模式串 needle[0..i] 的最長真前綴同時為後綴的長度。

構建 next 數組

vector<int> buildNext(const string& p) {
    int m = p.size();
    vector<int> nxt(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) j = nxt[j-1];
        if (p[i] == p[j]) ++j;
        nxt[i] = j;
    }
    return nxt;
}

KMP 匹配主循環

int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;
    auto nxt = buildNext(needle);
    for (int i = 0, j = 0; i < (int)haystack.size(); ++i) {
        while (j > 0 && haystack[i] != needle[j]) j = nxt[j-1];
        if (haystack[i] == needle[j]) ++j;
        if (j == (int)needle.size()) return i - j + 1;
    }
    return -1;
}

複雜度對比

面試建議

1. 先說明暴力思路及其缺點
2. 提出 KMP，解釋 next 數組含義與構建邏輯
3. 寫代碼前處理邊界情況（空串、長度比較）
4. 若面試官要求 O(1) 空間，可提及 Sunday/Two-Way 算法