力扣：串联所有单词的子串（滑动窗口+哈希）

首先，用 $\mathrm{n}$ 表示 $\mathrm{S}$ 串的长度，用 $\mathrm{m}$ 表示 $\mathrm{words}$ 的长度即words中单词的数量，用 $\mathrm{w}$ 表示 $\mathrm{words}$ 中每个单词的长度。
①对于 $\mathrm{S}$ 串以 $\mathrm{w}$ 为长度进行分割，则每一个 $\mathrm{w}$ 独立存在（可看成一个元素）。

②则有以 $i=0,1,\dots ,w-1$ 的 $\mathrm{w}$ 起点，看作 $\mathrm{w}$ 个组。
③在该串上，对每一个长度为 $\mathrm{w}$ 看作独立存在的元素，维护一个长度为 $\mathrm{m}$ 的滑动窗口，$\mathrm{j}$ 作为滑动窗口的结尾，用来维护长度。

④设 $\mathrm{map}$ 类型的 $\mathrm{tot}$ ，用来维护 $words$ 里面的单词所对应的数量。
在每一个组中，设 $\mathrm{map}$ 类型的 $\mathrm{wd}$ ，用来维护窗口内每个单词所对应的数量。
$\mathrm{cnt}$ 表示两个集合中同时存在的单词的数量
时间复杂度：
对每个视作独立元素做滑动窗口，nw\\rm \\frac{n}{w}wn​ 次滑动窗口移动,每次移动加一个元素，减一个元素，一共有 $\mathrm{w}$ 组，时间复杂度为 $O(n)$.

c++:

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> res;if(words.empty()) return res;int n = s.size(),m = words.size(),w = words[0].size();unordered_map<string,int> tot;for(auto& word : words) tot[word] ++;for(int i = 0;i < w;i++){int cnt = 0;unordered_map<string,int> wd;for(int j = i;j + w <= n;j += w){if(j >= i + m * w)//若超出滑动窗口的长度，则将以j结尾的窗口的前一个单词排出{auto word = s.substr(j - m * w,w);wd[word]--;//剔除的该单词在滑动窗口集合的数量小于words里面单词的数量，说明匹配的数量减少了if(wd[word] < tot[word]) cnt--;}auto word = s.substr(j,w);wd[word]++;//增加的单词在滑动窗口集合的数量增加之后依然没有超过words里单词的数量，说明满足条件的匹配的数量增加了if(wd[word] <= tot[word]) cnt++;if(cnt == m) res.push_back(j - (m - 1) * w);//当相应单词匹配的数量为m时，即匹配了words里所有的单词，则将滑动窗口起点加入答案。}}return res;}
};

学习计划指导