字串查找經典問題：在母串中尋找子串任意排列的首次出現位置

編輯：關於C語言

問題描述

給定一個母串 M 和一個子串 S。要求找出 S 的任意排列（即所有字元的全排列） 在 M 中首次出現的起始索引。若不存在，返回 -1。

範例：

M = "qwertyuihgfd"
S = "tyui"
輸出：4  // "tyui" 的排列 "yuit" 等在索引 4 開始處出現

核心洞察：滑動窗口 + 字元頻率匹配

由於 S 的排列數量隨長度呈階乘增長（n!），窮舉所有排列去匹配 M 完全不可行。關鍵觀察：

S 的任意排列在 M 中出現 ⟺ M 中存在一個長度為 |S| 的子串，其字元頻率統計與 S 完全一致。

因此，問題轉化為：在 M 中尋找長度固定為 |S| 的滑動窗口，使窗口內字元頻率表等於 S 的頻率表。

演算法步驟（O(N) 時間，O(Σ) 空間）

建立目標頻率表：遍歷 S，統計每個字元出現次數 → target[256]（或 unordered_map）。
初始化滑動窗口：取 M 前 |S| 個字元，建立窗口頻率表 window[256]。
滑動比對：
- 若 window == target → 返回當前起始索引。
- 否則，窗口右移一位：window[M[i]]--，window[M[i+|S|]]++，繼續比對。
遍歷結束未找到 → 返回 -1。

優化：避免每次全表比對

引入 matchCount 變數，記錄「當前窗口中與目標頻率一致的字元種類數」。

初始化時計算 matchCount。
滑動時，僅更新進出字元對應的計數，動態維護 matchCount。
當 matchCount == 目標字元種類數 時，即為匹配成功。比對降為 O(1)。

C++ 參考實現（含優化）

int findPermutation(const string& M, const string& S) {
    if (S.empty()) return 0;
    if (M.size() < S.size()) return -1;

    vector target(256, 0), window(256, 0);
    for (char c : S) target[(unsigned char)c]++;

    int required = 0;
    for (int cnt : target) if (cnt > 0) required++;

    int matchCount = 0;
    // 初始窗口 [0, S.size())
    for (size_t i = 0; i < S.size(); ++i) {
        unsigned char c = M[i];
        if (++window[c] == target[c]) matchCount++;
        else if (window[c] == target[c] + 1) matchCount--; // 超過目標
    }
    if (matchCount == required) return 0;

    // 滑動
    for (size_t i = S.size(); i < M.size(); ++i) {
        unsigned char out = M[i - S.size()];
        unsigned char in  = M[i];

        if (window[out] == target[out]) matchCount--;
        else if (window[out] == target[out] + 1) matchCount++; // 從超標變回標準
        window[out]--;

        if (++window[in] == target[in]) matchCount++;
        else if (window[in] == target[in] + 1) matchCount--;

        if (matchCount == required) return i - S.size() + 1;
    }
    return -1;
}