#include <unordered_map>
#include <iostream>
#include <vector>
std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
std::vector<int> result;
if (words.empty() || s.empty()) return result;
int wordLen = words[0].size();
int wordCount = words.size();
int totalLen = wordLen * wordCount;
// Frequency map of words
std::unordered_map<std::string, int> wordFreq;
for (auto &w : words) wordFreq[w]++;
// Sliding window approach
for (int i = 0; i <= (int)s.size() - totalLen; i++) {
std::unordered_map<std::string, int> seen;
int j = 0;
while (j < wordCount) {
std::string word = s.substr(i + j * wordLen, wordLen);
if (wordFreq.find(word) == wordFreq.end()) break;
seen[word]++;
if (seen[word] > wordFreq[word]) break;
j++;
}
if (j == wordCount) result.push_back(i);
}
return result;
}
int main() {
std::string s = "barfoofoobarthefoobarman";
std::vector<std::string> words = {"bar", "foo", "the"};
std::vector<int> indices = findSubstring(s, words);
// At index 6, the substring is: "foobarthe" = Concatenation of ["foo", "bar", "the"].
// At index 9, the substring is: "barthefoo" = Concatenation of ["bar", "the", "foo"].
// At index 12, the substring is: "thefoobar" = Concatenation of ["the", "foo", "bar"].
std::cout << "Output: [";
for (int i = 0; i < indices.size(); i++) {
std::cout << indices[i];
if (i != indices.size() - 1) std::cout << ",";
}
std::cout << "]" << std::endl;
}
/*
run:
Output: [6,9,12]
*/
