Can some one please explain how to solve this question ?
First of all precompute hashes of all substrings and store it in some kind of set where, hash[x][len] stores all the starting indices of all substrings having hash = x and length = len.
Binary search on the length len and for all i from 1 to n - len + 1, find the hash value x.
Check in the corresponding set hash[x][len] if there is any index greater than i + len which can be done by lower_bound in C++ and higherKey() function of TreeSet in Java.
And you are done.
Complexity : O(n^2) because of n^2 hashes precomputation.
Thanks a lot !! . Btw , does the solution accepts O(N^2) answer ?
I hope so, n = 5000.
1 Like
