30. Substring with Concatenation of All Words

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 算法 / Algorithm:
 * 把 s 切成「單字大小」的格子，對每個起始偏移 0..L-1 各跑一次滑動視窗。
 * 視窗以單字為步長前進，維護內部單字計數並與 need 比較，齊全時記錄起點。
 * Cut s into word-sized cells; for each offset 0..L-1 run one sliding window
 * that steps by whole words, keeps per-word counts, and records a start index
 * whenever the window holds exactly the required multiset of words.
 */

/* 雜湊表節點：把一個單字字串對應到整數 id / hash node: maps a word string to an int id */
typedef struct Entry {
    const char *word;     /* 指向某個 words[i]，長度為 wordLen / points into words[i], length wordLen */
    int id;               /* 此單字的編號 / this word's id */
    struct Entry *next;   /* 同一桶內的下一個節點（鏈結法解衝突）/ next node in same bucket (chaining) */
} Entry;

#define TABLE 16384       /* 桶數量，取 2 的次方 / number of buckets, a power of two */

/* djb2 字串雜湊，只看前 len 個字元 / djb2 string hash over the first len chars */
static unsigned long hashStr(const char *s, int len) {
    unsigned long h = 5381;                       /* 經典起始值 / classic seed value */
    for (int i = 0; i < len; i++)                 /* 逐字元混合 / fold each byte in */
        h = h * 33 + (unsigned char)s[i];         /* h*33 + 字元值 / h*33 + byte */
    return h;
}

/* 查單字的 id；create=1 時找不到就新建。回傳 id；create=0 且找不到回傳 -1。
 * Look up a word's id; if create=1, insert a new one. Returns id, or -1 when
 * create=0 and the word is absent. */
static int wordId(Entry **table, int *distinct, const char *word, int len, int create) {
    unsigned long h = hashStr(word, len) % TABLE; /* 算出桶的位置 / pick the bucket */
    for (Entry *e = table[h]; e != NULL; e = e->next)  /* 走訪這條鏈結 / walk the chain */
        if (memcmp(e->word, word, len) == 0)      /* 比較 len 個位元組是否相同 / compare len bytes */
            return e->id;                         /* 命中，回傳既有 id / hit */
    if (!create) return -1;                       /* 只查不建：回 -1 / lookup-only miss */
    Entry *e = (Entry *)malloc(sizeof(Entry));    /* 配置新節點 / allocate a node */
    e->word = word;                               /* 記住單字位址 / remember the word pointer */
    e->id = (*distinct)++;                        /* 指派下一個 id 並讓計數加一 / next id */
    e->next = table[h];                           /* 插到鏈頭 / prepend into bucket */
    table[h] = e;
    return e->id;
}

int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
    int n = (int)strlen(s);                       /* s 的長度 / length of s */
    int wordLen = (int)strlen(words[0]);          /* 每個單字長度（都相同）/ each word's length */
    int numWords = wordsSize;                     /* 單字數量 k / number of words */
    int totalLen = wordLen * numWords;            /* 完整拼接長度 / total match length */

    int *res = (int *)malloc(sizeof(int) * (n + 1)); /* 結果陣列，最多 n 個起點 / result, ≤ n starts */
    *returnSize = 0;                              /* 先記錄 0 個答案 / start with zero answers */
    if (totalLen > n) return res;                 /* 放不下就直接回空 / can't fit → empty */

    Entry **table = (Entry **)calloc(TABLE, sizeof(Entry *)); /* 桶陣列全設 NULL / all buckets NULL */
    int distinct = 0;                             /* 不同單字的個數 / number of distinct words */
    int *need = (int *)calloc(numWords, sizeof(int)); /* need[id] = 該單字需要幾個 / required count */
    for (int i = 0; i < numWords; i++) {          /* 建立需求表 / build the required counts */
        int id = wordId(table, &distinct, words[i], wordLen, 1); /* 取得/新建 id / get-or-create id */
        need[id]++;                               /* 需求加一 / one more required */
    }

    int *window = (int *)malloc(sizeof(int) * distinct); /* window[id] = 視窗內該單字數 / in-window count */

    for (int i = 0; i < wordLen; i++) {           /* 試每個起始偏移 0..L-1 / each starting offset */
        memset(window, 0, sizeof(int) * distinct);/* 清空視窗計數 / clear window counts */
        int left = i, cnt = 0;                    /* left=視窗左界, cnt=已配對單字數 / left edge & matched count */
        for (int right = i; right + wordLen <= n; right += wordLen) { /* 每次前進一個單字 / step one word */
            int id = wordId(table, &distinct, s + right, wordLen, 0); /* 右側單字的 id（不新建）/ right word's id */
            if (id == -1) {                       /* 不是目標單字 / not one of our words */
                memset(window, 0, sizeof(int) * distinct); /* 整個視窗作廢 / drop entire window */
                cnt = 0;
                left = right + wordLen;           /* 跳過壞單字、重新起算 / restart past the bad word */
                continue;
            }
            window[id]++;                         /* 把右側單字加入視窗 / add the right word */
            cnt++;
            while (window[id] > need[id]) {        /* 該單字數量超量了 / this word is over quota */
                int lid = wordId(table, &distinct, s + left, wordLen, 0); /* 最左單字 id / leftmost word id */
                window[lid]--;                    /* 從左邊移除一個 / drop one from the left */
                left += wordLen;
                cnt--;
            }
            if (cnt == numWords) {                /* 剛好湊齊所有單字 / window matches all words */
                res[(*returnSize)++] = left;      /* 記錄這個起點 / record start index */
                int lid = wordId(table, &distinct, s + left, wordLen, 0); /* 移除最左單字 / pop leftmost */
                window[lid]--;
                left += wordLen;                  /* 視窗右移，繼續找下一個 / slide and keep searching */
                cnt--;
            }
        }
    }

    for (int b = 0; b < TABLE; b++) {             /* 逐桶釋放鏈結節點 / free every chained node */
        Entry *e = table[b];
        while (e != NULL) { Entry *nx = e->next; free(e); e = nx; }
    }
    free(table);                                  /* 釋放桶陣列 / free buckets */
    free(need);                                   /* 釋放需求表 / free need */
    free(window);                                 /* 釋放視窗表 / free window */
    return res;                                   /* 回傳起點陣列 / return the indices */
}

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

/*
 * 算法 / Algorithm:
 * 對每個起始偏移 0..L-1 跑一次以單字為步長的滑動視窗，用 unordered_map 維護
 * 視窗內單字計數並與 need 比較；計數齊全時記錄起點。
 * For each offset 0..L-1, run a word-stepping sliding window. An unordered_map
 * tracks in-window word counts vs. need; record a start when the window is full.
 */
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;                           // 答案：起始索引 / answer: start indices
        int wordLen = words[0].size();             // 每個單字長度（都相同）/ each word's length
        int numWords = words.size();               // 單字數量 k / number of words
        int n = s.size();                          // s 的長度 / length of s
        int totalLen = wordLen * numWords;         // 完整拼接長度 / total match length
        if (totalLen > n) return res;              // 放不下就回空 / can't fit → empty

        // unordered_map：鍵→值的雜湊表，平均 O(1) 查詢。need[w] = 單字 w 需要幾個。
        // unordered_map is a hash map (avg O(1)). need[w] = how many of word w we need.
        unordered_map<string, int> need;
        for (const string& w : words)              // 範圍 for 走訪 words / range-for over words
            need[w]++;                              // 該單字需求加一 / one more required

        for (int i = 0; i < wordLen; i++) {        // 試每個起始偏移 / try each offset
            unordered_map<string, int> window;     // 視窗內每個單字的計數 / counts inside window
            int left = i, cnt = 0;                 // left=視窗左界, cnt=已配對數 / left edge & matched count
            for (int right = i; right + wordLen <= n; right += wordLen) { // 一次前進一個單字 / step one word
                string word = s.substr(right, wordLen); // 取出右側單字 / extract the right word
                if (need.find(word) == need.end()) {    // find 回傳 end() 代表不存在 / not a needed word
                    window.clear();                // 整個視窗作廢 / drop entire window
                    cnt = 0;
                    left = right + wordLen;        // 跳過壞單字、重啟 / restart past bad word
                    continue;
                }
                window[word]++;                    // 把右側單字加入視窗 / add the right word
                cnt++;
                while (window[word] > need[word]) {// 該單字超量 / this word over quota
                    string lw = s.substr(left, wordLen); // 最左單字 / leftmost word
                    window[lw]--;                  // 從左邊移除一個 / drop one from the left
                    left += wordLen;
                    cnt--;
                }
                if (cnt == numWords) {             // 剛好湊齊所有單字 / window matches all words
                    res.push_back(left);           // 記錄起點 / record start index
                    string lw = s.substr(left, wordLen); // 移除最左單字 / pop leftmost
                    window[lw]--;
                    left += wordLen;               // 視窗右移繼續找 / slide and keep searching
                    cnt--;
                }
            }
        }
        return res;                                // 回傳所有起點 / return all start indices
    }
};