#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
    }
};