Leetcode 30 - concatenate all strings in dictionary - source code from blog: https://yujia.io/blog/2015/11/17/LeetCode-30-Substring-with-Concatenation-of-All-Words/

Leetcode30_contatenatingAllStrings1.cpp

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int l_dict = words.size(), l_s = s.size();
        vector<int> result;
        if (!l_dict || !l_s)
            return result;
        unordered_map<string, int> dict;
        for (int i = 0; i < l_dict; i++)
            dict[words[i]]++; //Use the property that the default value of int in unordered map is zero
        int len = words[0].size(); // Each word has the same length!!! 
        for (int i = 0; i < len; i++){
            unordered_map<string, int> cur_dict;
            int start = i;
            int cur_words = 0;
            for(int j = i; j <= l_s-len ; j += len){
                auto cur_str = s.substr(j,len);
                if (dict.find(cur_str) != dict.end()){
                    cur_dict[cur_str]++;
                    cur_words++;
                    while (cur_dict[cur_str] > dict[cur_str]){
                        cur_dict[s.substr(start,len)]--;
                        start += len;
                        cur_words--;
                    }
                    if (cur_words == l_dict){
                        result.push_back(start);
                        cur_dict[s.substr(start,len)]--;
                        cur_words--;
                        start += len;
                    }
                }else{
                    start = j+len;
                    cur_words = 0;
                    cur_dict.clear();
                }
            }
        }
        return result;
    }
};