# Share my 54ms solution

• based on rolling hash, plus multi-window, here is my 54ms solution.

``````class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> result;
if (L.empty() || L[0].empty() ) return result;
if (S.size() < L.size() * L[0].size()) return result;

const int lsize = L.size();
const int wsize = L[0].size();
const int gsize = lsize * wsize;
const int r = 31;
const int q = 997;
const int m = 3355439;

int lhash = 0;
for (int i = 0; i<lsize; i++) {
int whash = 0;
for (int j=0; j<wsize; j++) {
whash = (whash * r + L[i][j]) % q;
}
lhash = (lhash + whash) % m;
}

vector<int > ghashes(wsize);
vector<int> window(gsize);
int whead = 0;

int whash = 0;
int i = 0;
int weight = 1;
for (; i<wsize-1; i++) {
whash = (whash * r + S[i]) % q;
weight = (weight * r) % q;
}

unordered_multiset<string> Lset(L.begin(), L.end());
for (; i<S.size(); i++) {
int &ghash = ghashes[whead % wsize];
ghash = (ghash - window[whead] + m) % m;
window[whead] = whash = (whash * r + S[i]) % q;
ghash = (ghash + whash) % m;
whash = (whash - (S[i-wsize+1] * weight) % q + q) % q;

if (ghash == lhash && match(S, i-gsize+1, Lset))
result.push_back(i - gsize + 1);
}

return result;
}

bool match(const string &S, int pos, unordered_multiset<string> L) {
if (pos < 0) return false;

const int lsize = L.size();
const int wsize = L.begin()->size();
for (int i=0; i<lsize; i++) {
auto iter = L.find(S.substr(pos, wsize));
if (iter == L.end()) return false;
L.erase(iter);
pos += wsize;
}
return true;
}
};``````

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