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.
Thanks!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.
Thanks!