class Solution {

public:

    vector<int> findSubstring(string s, vector<string>& words) {

        vector<int>res;

        if(words.empty()||s.empty())

            return res;

        map<string,int>allWords;

        int wordLen=words[0].size();

        int wordNum=words.size();

        for(int i=0;i<wordNum;i++)

        {

            if(allWords.find(words[i])!=allWords.end())

                allWords[words[i]]++;

            else

                allWords.insert(make_pair(words[i],1));

        }

    bool hasRemoved=false;

    map<string, int> hasWords;

    //将所有移动分成 wordLen 类情况 即从i=0,1,2...wordLen-1处开始，每次移动WordLen长度

    for (int j = 0; j < wordLen; j++) {

        hasWords.clear();

        int num = 0; //记录当前hasWords中有多少个单词

        for (int i = j; i +wordNum * wordLen< s.length()+1; i = i + wordLen) { //每次判断一个窗口，窗口从i开始长                                                                      wordNum * wordLen         窗口每次移动一个单词长度

            hasRemoved = false; //防止情况三移除后，情况一继续移除

            while (num < wordNum) {

                string word = s.substr(i + num * wordLen,wordLen);

                if (allWords.find(word)!=allWords.end()) {

                    if(hasWords.find(word)!=hasWords.end())

                        hasWords[word]++;

                    else

                        hasWords.insert(make_pair(word,1));

                    //遇到了符合的单词，但是次数超了

                    if (hasWords[word] > allWords[word]) {

                        hasRemoved = true;

                        int removeNum = 0;

                        //一直移除单词，直到次数符合了

                        while (hasWords[word] > allWords[word]) {

                            string firstWord = s.substr(i + removeNum * wordLen,wordLen);

                            hasWords[firstWord]-=1;

                            removeNum++;

                        }

                        num = num - removeNum + 1; //加 1 是因为我们把当前单词加入到了 HashMap 2 中

                        i = i + (removeNum - 1) * wordLen; //这里依旧是考虑到了最外层的 for 循环，看情况二的解释

                        break;

                    }

                //出现情况二，遇到了不匹配的单词，直接将 i 移动到该单词的后边（但其实这里

                //只是移动到了出现问题单词的地方，因为最外层有 for 循环， i 还会移动一个单词

                //然后刚好就移动到了单词后边）

                } else {

                    hasWords.clear();

                    i = i + num * wordLen;

                    num = 0;

                    break;

                }

                num++;

            }

            if (num == wordNum) {

                res.push_back(i);

            }

            //出现情况一，子串完全匹配，我们将上一个子串的第一个单词从 HashMap2 中移除

            if (num > 0 && !hasRemoved) {

                string firstWord = s.substr(i,wordLen);

                hasWords[firstWord]-=1;

                num = num - 1;

            }

        }

    }

        return res;

    }

};