Substring Concatenation

• Time : O(B + |A|)
• Space : O(B)

c++

vector<int> Solution::findSubstring(string A, const vector<string> &B) {
    int len = B[0].length(), n = A.length(), m = B.size();
    if(n < len * m) return {};
    unordered_map<string, int> freq;
    for(auto& b : B) freq[b]++;
    
    vector<int> res;
    for(int i = 0; i < len; i++) {
        unordered_map<string, int> window;
        int match = 0;
        for(int j = 0; i + (j + 1) * len <= n; j++) {
            string sub = A.substr(i+j*len, len);
            if(freq.count(sub) and ++window[sub] == freq[sub]) match++;
            if(j >= m) {
                string rsub = A.substr(i + (j-m)*len, len);
                if(freq.count(rsub) and --window[rsub] + 1 == freq[rsub]) match--;
            }
            if(match == freq.size()) res.push_back(i + (j-m+1)*len);
        }
    }
    return res;
}