34 lines
923 B
C++
34 lines
923 B
C++
#include "s0030_substring_with_concatenation_of_all_words.hpp"
|
|
|
|
vector<int> S0030::findSubstring(string s, vector<string>& words) {
|
|
vector<int> res;
|
|
int m = words.size(), n = words[0].size(), ls = s.size();
|
|
for (int i = 0; i < n && i + m * n <= ls; ++i) {
|
|
unordered_map<string, int> differ;
|
|
for (int j = 0; j < m; ++j) {
|
|
++differ[s.substr(i + j * n, n)];
|
|
}
|
|
for (string& word : words) {
|
|
if (--differ[word] == 0) {
|
|
differ.erase(word);
|
|
}
|
|
}
|
|
for (int start = i; start < ls - m * n + 1; start += n) {
|
|
if (start != i) {
|
|
string word = s.substr(start + (m - 1) * n, n);
|
|
if (++differ[word] == 0) {
|
|
differ.erase(word);
|
|
}
|
|
word = s.substr(start - n, n);
|
|
if (--differ[word] == 0) {
|
|
differ.erase(word);
|
|
}
|
|
}
|
|
if (differ.empty()) {
|
|
res.emplace_back(start);
|
|
}
|
|
}
|
|
}
|
|
return res;
|
|
}
|