vector<int> findSubstring(string str, vector<string>& words) {
    if (words.empty()) {
        return {};
    }
    int n = str.size(), m = words.size(), w = words[0].size();

    unordered_map<string, int> hashMap;
    for (int i = 0; i < m; i++ ) {
        hashMap[words[i]]++;
    }

    vector<int> res;
    for (int k = 0; k < w; k++) {
        unordered_map<string, int> myMap;
        int cnt = 0;
        int i = k;
        for (int j = i; j + w <= n; j += w) {
            string word;
            // pop_front
            if (j - m * w >= i) {
                word = str.substr(j - m * w, w);
                if (hashMap.find(word) != hashMap.end()) {
                    myMap[word]--;
                    if (myMap[word] >= 0 && myMap[word] < hashMap[word]) {
                        cnt--;
                    }
                }
            }

            // push_back
            word = str.substr(j, w);
            if (hashMap.find(word) == hashMap.end()) {
                cnt = 0;
                myMap.clear();
                i = j + w;
            } else {
                myMap[word]++;
                if (myMap[word] > 0 && myMap[word] <= hashMap[word]) {
                    cnt++;
                }
            }

            if (cnt == m) {
                res.push_back(j - (m - 1) * w);
            }
        }
    }
    return res;
}