Skip to content

Instantly share code, notes, and snippets.

@barrysteyn
Last active December 20, 2015 07:19
Show Gist options
  • Save barrysteyn/6092715 to your computer and use it in GitHub Desktop.
Save barrysteyn/6092715 to your computer and use it in GitHub Desktop.
LeetCode: Substring with concatenation of all words (http://leetcode.com/onlinejudge#question_30)
/*
* This is a very cool method to perform the leetcode task.
* It is time O(n) (n being the size of string S) if it is
* implemented with an unordered_map on line 65, otherwise it
* is O(n*log(m)) (m being the size of the vector L)
*
* This method demonstrates how hashes can be used for
* comparison instead of strings. It is inspired by
* the topcoder article: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
*/
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
class Substring {
private:
int base,
prime;
//Will return the correct mod, even if a is negative
int int_mod(int a, int b) {
return (a%b + b)%b;
}
//Needed for the rolling has, it is the chosen numeral to the power of m-1
int baseM_1(int m) {
int base_1 = 1;
for (int i=0; i < m; i++) {
base_1 = int_mod(base_1*base, prime);
}
return base_1;
}
//Implements a rolling hash: See http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
int rollingHash(const string& input, int lastPos, int currentPos, int currentHash, int baseM_1) {
if (lastPos >= 0) {
currentHash = int_mod(currentHash - int_mod(input[lastPos]*baseM_1, prime), prime);
}
currentHash = int_mod(currentHash*base, prime);
currentHash = int_mod(currentHash + input[currentPos], prime);
return currentHash;
}
public:
Substring() :
base(26), //base is chosen as the size of my alphabet (in this case, latin alphabet lowercase = 26)
prime(6291469) //a largish prime number for hashing (found from here: http://planetmath.org/goodhashtableprimes)
{};
vector<int> findSubstring(string S, vector<string> &L) {
int stringHashCurrent = 0,
stringHashBehind = 0,
substringHash = 0,
m = L[0].size(),
lSize = m*L.size(),
bm_1 = baseM_1(m-1),
index = 0;
map<int, bool> substringHashPresent;
vector<int> substring(m,0),
substringSize(m,0);
vector<int> indices;
//Build a hash for each substring
for (int i=0; i < L.size(); i++) {
int tempSubstringHash = 0;
for (int j=0; j < m; j++) {
tempSubstringHash = rollingHash(L[i], -1, j, tempSubstringHash, bm_1);
}
substringHashPresent[tempSubstringHash] = true;
substringHash = int_mod(substringHash + tempSubstringHash, prime);
}
//Try Compare That Hash To Each Substring
for (int i=0; i < S.size(); i++) {
stringHashCurrent = rollingHash(S, ((i < m) ? -1 : i -m), i, stringHashCurrent, bm_1);
if (i < m-1)
continue;
index = i%m;
if (i >= lSize) {
stringHashBehind = rollingHash(S, ((i-lSize-m < 0) ? -1 : i-lSize-m), i-lSize, stringHashBehind, bm_1);
}
if (substringHashPresent[stringHashCurrent]) {
int tempHash = int_mod(substring[index]+stringHashCurrent, prime);
substringSize[index] += m;
if (substringSize[index] > lSize) {
tempHash = int_mod(tempHash - stringHashBehind, prime);
}
if (tempHash == substringHash) {
indices.push_back(i-(lSize-1));
}
substring[index] = tempHash;
} else {
substringSize[index] = 0;
substring[index] = 0;
}
}
return indices;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment