首页 > 代码库 > Substring with Concatenation of All Words -- leetcode
Substring with Concatenation of All Words -- leetcode
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9]
.
(order does not matter).
利用滚动Hash,接合窗口移动,完成下面这个算法。
思想是,先计算出Hash值,用Hash值完成在map中的查找,最后用字符串精确匹配最验证。
并尽可能推迟并省掉字符串精确匹配。
这个算法虽然被leetcode AC了。 但是实际运行时间并预想的慢多了,高达1272ms。
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> result; if (L.empty()) return result; const int itemSize = L[0].size(); const int wndSize = itemSize * L.size(); const int q = 3355439; const int r = 256; map<int, vector<int> > map1; for (int i=0; i<L.size(); i++) { int nHash = 0; for (int j=0; j<L[i].size(); j++) { nHash = ((nHash * r) % q + L[i][j]) % q; } map1[nHash].push_back(i); } vector<int> total(itemSize); vector<int> revMap(wndSize); vector<pair<int,bool> > map2(wndSize); int head2 = 0; int weight = 1; for (int i=1; i<itemSize; i++) weight = (weight * r) % q; int nHash = 0; for (int i=0; i<itemSize-1; i++) nHash = ((nHash * r) % q + S[i]) % q; for (int i=itemSize-1; i<S.size(); i++) { const int group = i % itemSize; const int offset = group * L.size(); if (map2[head2].first) { revMap[offset + map2[head2].first - 1] = 0; map2[head2].first = 0; map2[head2].second = false; --total[group]; } nHash = ((nHash * r) % q + S[i]) % q; map<int, vector<int> >::iterator iter = map1.find(nHash); if (iter != map1.end()) { int pos = -1; bool compare = true; const vector<int> &val = (*iter).second; if (val.size() == 1) { const int entry = revMap[offset + val[0]]; if (!entry || !S.compare(i-itemSize+1, itemSize, L[val[0]])) { pos = 0; compare = !!entry; } } else { compare = true; int min = i+1; for (int j=0; j<val.size(); j++) { if (!S.compare(i-itemSize+1, itemSize, L[val[j]])) { const int entry = revMap[offset + val[j]]; if (!entry) { pos = j; break; } else if (entry < min) { min = entry; pos = j; } } } } if (pos != -1) { const int entry = revMap[offset + val[pos]]; revMap[offset + val[pos]] = i + 1; map2[head2].first = val[pos] + 1; map2[head2].second= compare; total[group]++; if (entry) { const int entry2 = (head2 - i + entry - 1 + wndSize) % wndSize; map2[entry2].first = 0; map2[entry2].second= false; total[group]--; } if (total[group] == L.size()) { for (int j=0; j<L.size(); j++) { const int entry2 = (head2 - i + revMap[offset+j] - 1 + wndSize) % wndSize; if (!map2[entry2].second) { if (!S.compare(revMap[offset+j]-itemSize, itemSize, L[j])) { map2[entry2].second = true; } else { revMap[offset+j] = 0; map2[entry2].first = 0; map2[entry2].second= false; total[group]--; break; } } } if (total[group] == L.size()) result.push_back(i-wndSize+1); } } } nHash = ((nHash - (S[i-itemSize+1] * weight) % q) % q + q) % q; head2 = (head2 + 1) % wndSize; } return result; } };
Substring with Concatenation of All Words -- leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。