题解 | #牛牛的串联子串游戏#

**解题思路：**已知s一定是有任意个words中的word组成的。先建立一个map对应words中每个字符串对应的个数，那么我们只需在滑动窗口内依次分割出每个word， 判断其是否在words中/个数是否超过words中对应的个数，因为s中均为word组成，所以如果有不存在的word或者某个word的个数多余words中的个数，那么就是不符合的，其余情况均符合，此时记录滑动窗口起始位置即可。

class Solution {
  public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;

        if (words.empty() || s.empty()) {
            return res;
        }

        int slen = s.size(); // 字符串s的长度
        int wordNum = words.size(); // 单词数组words中的单词数量
        int wordLen = words[0].size(); // 单词数组中的单词长度（假设所有单词长度相同）
        int totalLen = wordNum * wordLen; // 所有单词连接后的总长度

        unordered_map<string, int> targetMap;
        for (auto word : words) {
            targetMap[word]++; // 统计单词数组中每个单词出现的次数
        }

        for (int i = 0; i <= slen - totalLen; i += wordLen) {
            // 从字符串s的第i个位置开始遍历，每次移动一个单词长度
            unordered_map<string, int> curMap;
            int j = 0;

            for (; j < wordNum; j++) {
                // 从当前位置开始，截取一个单词长度的子串
                string word = s.substr(i + j * wordLen, wordLen);
                if (targetMap.find(word) != targetMap.end()) {
                    // 如果子串在目标单词统计map中存在
                    curMap[word]++; // 更新当前子串的出现次数
                    if (curMap[word] > targetMap[word]) {
                        // 如果超过了目标单词统计map中该单词的出现次数
                        break; // 结束遍历，当前位置不符合要求
                    }
                } else {
                    // 如果子串不在目标单词统计map中
                    break; // 结束遍历，当前位置不符合要求
                }
            }

            if (j == wordNum) {
                // 如果遍历完所有单词，说明当前位置满足要求
                res.push_back(i); // 记录符合要求的起始位置
            }
        }

        return res;
    }
};