#include
#include
#include <unordered_map>
using namespace std;
vector findSubstring(string s, vector& words) {
unordered_map<string, int> map;
for (string word : words) {
map[word] = map.size();
}
vector counts(map.size(), 0);
for (string word : words) {
counts[map[word]]++;
}
vector res;
int sLen = s.size();
int wordNum = words.size();
int wordLen = words[0].size();
int len = wordLen * wordNum;
for (int i = 0; i < wordLen; i++) {
for (int j = i; j <= sLen - len; j += wordLen) {
vector windows(map.size(), 0);
for (int k = wordNum - 1; k >= 0; k--) {
int begin = j + k * wordLen;
string word = s.substr(begin, wordLen);
int index = -1;
if (map.count(word) > 0) {
index = map[word];
}
if (index == -1 || windows[index]++ == counts[index]) {
j = begin;
break;
}
if (k == 0) {
res.push_back(j);
}
}
}
}
return res;
}
int main() {
string s = "barfoothefoobarman";
vector words = {"foo", "bar"};
vector result = findSubstring(s, words);
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
