1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        std::vector<int> res;
        if (words.empty())  // 边界情况：words为空
            return res;

        int n = s.size();             // 字符串 s 的长度
        int m = words.size();         // 单词个数
        int w = words[0].size();      // 单词长度

        // 统计 words 中每个单词出现的次数
        std::unordered_map<std::string, int> total;
        for (std::string& word : words)
            ++ total[word];

        // 遍历所有可能的起始位置（避免跨单词边界）
        for (int i = 0; i < w; ++i)
        {
            std::unordered_map<std::string, int> window;  // 窗口内单词频次
            int cnt = 0;  // 匹配到的单词数

            // 滑动窗口，步长为 w（单词长度）
            for (int j = i; j + w <= n; j += w)
            {
                // 当前窗口右侧加入新单词
                std::string rightWord = s.substr(j, w);
                ++ window[rightWord];
                if (window[rightWord] <= total[rightWord])  // 新单词未超额
                    ++ cnt;

                // 如果窗口超过了大小 m * w，滑动窗口左侧
                if (j >= i + m * w)
                {
                    std::string leftWord = s.substr(j - m * w, w);
                    -- window[leftWord];
                    if (window[leftWord] < total[leftWord])  // 如果减少后不匹配
                        -- cnt;
                }

                // 匹配到所有单词，记录起始索引
                if (cnt == m)
                    res.push_back(j - (m - 1) * w);
            }
        }
        return res;
    }
};