re: Advent of code Day 2 Part 2 Complexity VIEW POST

re: 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 cons...

Awesome! I will study this possibility later! I didn't know this algorithm and get back here tell how did I fare. The reason I am trying to make this < O(N2) is just because it seemed interesting not for some specific requisite of the problem, I imagined that the input wasn't big enough to justify all this effort.


Gotcha! It’s great to challenge ourselves to see if we can go one step beyond. Please let me know if you can find out something!

One limitation that I just thought with this algorithm is that it had been originally used to search subsequent characters inside a bigger string. But in our case, any char can be different, so we might need to look at the whole substring (which happens to have the same size as every other string) and hence maybe we won’t be able to get down to O(N).

But maybe there’s a way to create a very clever hash function that would work regardless of this limitation so we don’t need to manually compare each char. But I might be overlooking this.


code of conduct - report abuse