# Really C++ O(n) 26ms solution using precomputed hashes.

• ``````const int MAGICK = 31;

// polynomial hash of the first k characters
// O(k) time, O(1) mem
int poly_hash(string const& s, int k) {
int sum = 0;
for (int i = 0; i < k; ++i) {
sum *= MAGICK;
sum += s[i];
}
return sum;
}

// compute hash of every substring of length k
// O(n) time, O(n - k) mem, n = s.length()
vector<int> precompute_hashes(string const& s, int k) {
assert(k <= s.size());
vector<int> result(s.size() - k + 1);
int sum = poly_hash(s, k);
int acc = 1;
for (int i = 0; i < k - 1; i++) {
acc *= MAGICK;
}

// sliding windows of size k starting at i
for (int i = 0; i + k <= s.size(); ++i) {
result[i] = sum;
sum -= s[i] * acc;
sum *= MAGICK;
if (i + k < s.size())
sum += s[i + k];
}

return result;
}

// assuming key in map,
// decrease value of map[key]
// if value drops to 0, delete key from map
void decrease_key(unordered_map<int, int>& map, int key) {
auto it = map.find(key);
if (--it->second == 0)
map.erase(it);
}

class Solution {
public:
// O(n) time, O(n) mem
vector<int> findSubstring(string s, vector<string> const& words) {
vector<int> result;
int n = s.length(), m = words.size();
if (n == 0 || m == 0)
return result;
int k = words[0].length();
int words_len = k * m;
if (k == 0 || words_len > n)
return result;

// O(n)
auto hashes = precompute_hashes(s, k);

// O(words_len) time
unordered_map<int, int> word_count;
for (auto const& word: words) {
++word_count[poly_hash(word, word.length())];
}
const auto not_found = word_count.end();

// O(k) * O(n / k) * O(1) = O(n)
for (int i = 0; i < k; ++i) {
unordered_map<int, int> count;
int start = i;
if (start + words_len > n)
return result;
for (int j = i; j + k <= n; j += k) {
auto it = word_count.find(hashes[j]);
if (it != not_found) {
// how many words with hashes[j] are left to find
int to_find = it->second - (++count[hashes[j]]);
if (to_find > 0)
continue;
if (to_find == 0) {
// check if we found a solution
// if so, move start to next word
if (start + words_len == j + k) {
result.push_back(start);
decrease_key(count, hashes[start]);
start += k;
}
continue;
}
// to_find < 0
// move start to the position where to_find == 0
while (hashes[start] != hashes[j]) {
decrease_key(count, hashes[start]);
start += k;
}
decrease_key(count, hashes[j]);
start += k;
if (start + words_len > n)
break;
continue;
}
start = j + k;
if (start + words_len > n)
break;
count.clear();
}

}

return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.