您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

字串排列組合查找：在母串中尋找子串任意排列的首次出現位置

編輯：關於C

問題定義

給定母串 `M` 與子串 `S`，找出 `S` 的**任意排列**（anagram）在 `M` 中**首次出現**的起始索引。若不存在，回傳 -1。

範例：`M = "qwertyuihgfd"`, `S = "tyui"` → 輸出 `4`（`M[4..7] = "tyui"` 正是 `S` 的一種排列）

核心觀察

子串排列數 `k!` 指數級增長，**不可枚舉所有排列去匹配**
**滑動窗口 + 字元頻率統計** 是標準解法：固定窗口長度 `|S|`，統計窗內字元頻率與 `S` 比對
原文提供的 C# 方案：**逐窗口檢查、用 List 移除匹配字元**，邏輯正確但效率較低（O(n·m²)）

原文 C# 實作分析


string M = "abcbdedbcbcbbcbbbc";
string S = "bcb";
List indices = new List();

for (int i = 0; i <= M.Length - S.Length; i++) {
    string window = M.Substring(i, S.Length);
    List chars = new List(S.ToCharArray()); // 複製 S 字元表

    for (int j = 0; j < window.Length; j++) {
        if (chars.Contains(window[j])) {
            chars.Remove(window[j]); // 匹配則移除
        } else {
            break; // 失敗，提前終止內層迴圈
        }
        if (j == window.Length - 1) // 內層完整跑完
            indices.Add(i);
    }
}
foreach (int idx in indices)
    Console.WriteLine($"string is {M.Substring(idx, S.Length)} index: {idx}");

優缺點評析

優點	缺點
邏輯直觀，易理解	`Contains` + `Remove` 皆 O(m)，總複雜度 O(n·m²)
找出所有匹配位置	每窗口 `new List` 分配記憶體，GC 壓力大
提前 `break` 剪枝	未利用字元頻率陣列 O(1) 查找優勢

最優解法：滑動窗口 + 固定頻率陣列 (O(n + m))

假設字元集為 ASCII（128）或擴展 ASCII（256），用固定大小陣列統計頻率。

C 語言實作


#include 
#include 
#include 

#define CHARS 128 // ASCII

int find_anagram(const char *M, const char *S) {
    int lenM = strlen(M), lenS = strlen(S);
    if (lenS > lenM) return -1;

    int target[CHARS] = {0}, window[CHARS] = {0};
    for (int i = 0; i < lenS; i++) target[(unsigned char)S[i]]++;

    // 初始化第一個窗口
    for (int i = 0; i < lenS; i++) window[(unsigned char)M[i]]++;

    if (memcmp(target, window, sizeof(target)) == 0) return 0;

    // 滑動窗口
    for (int i = lenS; i < lenM; i++) {
        window[(unsigned char)M[i]]++;           // 進窗口
        window[(unsigned char)M[i - lenS]]--;    // 離窗口
        if (memcmp(target, window, sizeof(target)) == 0)
            return i - lenS + 1;
    }
    return -1;
}

int main() {
    const char *M = "qwertyuihgfd";
    const char *S = "tyui";
    int pos = find_anagram(M, S);
    printf("First anagram at index: %d\n", pos); // 輸出 4
    return 0;
}

關鍵優化點

頻率陣列比較：`memcmp` 單指令比較 128/256 bytes，極快
滑動更新 O(1)：只增減進出字元，無需重掃窗口
無額外分配：棧上固定陣列，零 GC

進一步優化：匹配計數器避免 memcmp


int diff = 0; // 記錄有多少字元頻率不匹配
// 初始化 diff
for (int c = 0; c < CHARS; c++)
    if (target[c] != window[c]) diff++;

if (diff == 0) return 0;

// 滑動時增量維護 diff
char in = M[i], out = M[i - lenS];
if (++window[in] == target[in]) diff--;
else if (window[in] == target[in] + 1) diff++;

if (--window[out] == target[out]) diff--;
else if (window[out] == target[out] - 1) diff++;

if (diff == 0) return i - lenS + 1;

將窗口比較從 O(CHARS) 降為 O(1)，總複雜度嚴格 O(n)。

C++ STL 版本（生產碼推薦）


#include 
#include 
#include 

int findAnagram(const std::string& M, const std::string& S) {
    if (S.size() > M.size()) return -1;
    std::array target{}, window{};
    for (char c : S) target[(unsigned char)c]++;

    for (size_t i = 0; i < S.size(); i++) window[(unsigned char)M[i]]++;
    if (target == window) return 0;

    for (size_t i = S.size(); i < M.size(); i++) {
        window[(unsigned char)M[i]]++;
        window[(unsigned char)M[i - S.size()]]--;
        if (target == window) return i - S.size() + 1;
    }
    return -1;
}

`std::array` 支援 `==` 直接比較，碼簡潔且零開銷。

複雜度對比總結

方法	時間複雜度	空間複雜度	適用場景
原文 List 移除法	O(n·m²)	O(m)	教學、極短字串
頻率陣列 + memcmp	O(n·CHARS)	O(CHARS)	通用、ASCII/UTF-8 兼容
頻率陣列 + diff 計數器	O(n)	O(CHARS)	高效能、長字串、競程
雜湊表 (Unicode)	O(n) 期望	O(k) k=不同字元數	大字元集、Unicode

邊界情況處理

`S` 為空串 → 回傳 0（空串是任意位置的子序列）
`M` 為空、`|S| > |M|` → 回傳 -1
字元簽名：`(unsigned char)` 強轉避免負索引
大小寫敏感：如需不敏感，預先 `tolower` 統一

總結

「子串任意排列查找」本質是**固定長度窗口下的多集合相等判定**。原文 C# 方案邏輯正確但非最優；工業級解法採用滑動窗口 + 字元頻率陣列 + 增量匹配計數器，達到 O(n) 時間、O(1) 空間（字元集固定時）。理解從「枚舉排列」到「統計頻率」的思維轉折，是解決所有 anagram 類問題的關鍵。