LC

题目

思路 $O(nw)$

本题有一个比较强的性质：所有的模式串都是定长的

这也是能够利用滑窗模型优化的一个前提

判断滑窗框起来的单词是否全部有效，不需要一 一比较。可以维护一个计数器记录当前窗口内有效的单词，当计数器计满时存一下答案即可。

复杂度分析：

设s串长度为$n$，每个单词长度为$w$。

  • s串一共被分割成$\frac{n}{w}$个单词，因此需要枚举$O(\frac{n}{w})$次；
  • 取出每个单词（substr操作）是$O(w)$的；
  • 枚举i需要$O(w)$

总的时间复杂度为：$O(nw) $

图1

代码

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> hash;
        for(auto &word : words) hash[word]++;

        for(int i = 0; i < w; i++) {
            unordered_map<string, int> wd;
            int cnt = 0;
            for(int j = i; j + w <= n; j += w) {
                if(j >= i + m * w) {  // 需要去掉窗口开头的单词
                    string word = s.substr(j - m * w, w); 
                    wd[word]--;
                    if(wd[word] < hash[word]) cnt--;
                }
                string word = s.substr(j, w);
                wd[word]++;
                if(wd[word] <= hash[word]) cnt++;
                if(cnt == m) res.push_back(j - (m - 1) * w); // 此时的j还没加w，所以只需减去(m - 1)倍的w即可获取窗口开头单词的下标

            }
        }
        return res;
    }
};