## DEV Community is a community of 789,560 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Advent of code Day 2 Part 2 Complexity

Tiago Romero Garcia

I have been also wrapping my head around that.

I tried tinkering around with Robin-Karp algorithm but because we have to take the order into consideration, we would have to build a clever hash function that also takes the order into consideration. So we could maybe get it down to O(N).

I didn't try too hard but it also crossed my mind the same think that @aspittel said, the size input is small and hence it won't really matter to the point of getting it resolved and proceed on AoC.

But just for curiosity sake I was planning to get back at that sometime later.

I have a JS implementation of this Robin-Karp algorithm as one of the exercises from "Cracking the Code Interview, 6th Ed", here you go:

``````// Robin-karp substring search with rolling hash function
function substringSearch(string, substring) {
const stringLength = string.length;
const substringLength = substring.length;

// Generating hashes
const hashes = [calculateHash(string, substringLength)];
for (let i = 1; i < stringLength - substringLength; i++) {
hashes[i] = updateHash(string, substringLength, hashes[i-1], i-1);
}
const substringHash = calculateHash(substring, substringLength);

// Comparing hashes
for (let i = 0; i < stringLength - substringLength; i++) {
const index = i + substringLength;
if (hashes[i] === substringHash && compare(string, i, substring)) {
return i;
}
}

return -1;
}

function calculateHash(string, length, startIndex = 0) {
let hash = 0;
for (let i = startIndex, power = length-1; i < length; i++, power--) {
hash += string.charCodeAt(i) * Math.pow(128, power);
}
return hash;
}

function updateHash(string, length, hash, outcomingIndex) {
return (hash - string.charCodeAt(outcomingIndex) * Math.pow(128, length-1)) * 128 + string.charCodeAt(outcomingIndex + length);
}

function compare(string, index, substring) {
const stringLength = string.length;
const substringLength = substring.length;

if (index + substringLength > stringLength) {
return false;
}

for (let i = index, j = 0; i < stringLength && j < substringLength; i++, j++) {
if (string.charAt(i) !== substring.charAt(j)) {
return false;
}
}

return true;
}

console.log(substringSearch('doe are hearing me', 'ear'));
``````