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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param words string字符串vector 
     * @return int整型vector
     */
    vector<int> findSubstring(string s, vector<string>& words) {
        // write code here
        int k = words[0].size();
        int n = words.size();
        int i = 0;
        // map记录words
        map<string, int> dict;
        for (auto item : words) {
            if (dict.find(item) == dict.end()) {
                dict.emplace(item, 1);
            }
            else ++dict[item];
        }

        vector<int> res;
        int start = 0;
        i = n * k;
        // 用前n个字符串初始化
        for (int j = 0; j < i; j += k)
        {
            string substr = s.substr(j, k);
            if (dict.find(substr) != dict.end()) --dict[substr];
        }
        bool judge = true;
        for (auto it : dict)
        {
            judge &= (it.second == 0);
        }
        if (judge) res.push_back(start);

        while (i < s.size())
        {
            // 处理当前字符串
            string substr = s.substr(i, k);
            if (dict.find(substr) != dict.end()) --dict[substr];
            substr = s.substr(start, k);
            if (dict.find(substr) != dict.end()) ++dict[substr];
            i += k;
            start += k;

            bool judge = true;
            for (auto it : dict)
            {
                judge &= (it.second == 0);
            }
            if (judge) res.push_back(start);
        }
        return res;
    }
};