The Gift Of Raksha Bandhan
PROBLEM LINK
Author: Md Shakim
Tester: Shekhar Nain
DIFFICULTY
Easy
PREREQUISITES
Z-Algorithm , String Hashing , Binary Search.
PROBLEM
You are given a string S of length L and Q queries in form of a index P.
You need to calculate LCP(Longest Common Prefix) of the two parts ie first part is [0,P-1] and second part is [P,L-1].
QUICK EXPLANATION
This question can be solved by direct application of Z-algorithm in O(N+Q) time
This question can also be solved by Binary Search + Rabin Karp Hashing(Rolling Hash) in O(Q*logN) time.
NOTE: Suffix Array solution of this question has a complexity of O(NlogN + Q) time. This will not pass as Nlogn construction of suffix array will time out.
EXPLANATION
First we will see the solution using Z-Algorithm.
This algorithm takes a string[0,L-1] as an input and gives a array called Z-array[0,L-1] as output.
Z[p] (where p varies from 1 to L-1) gives the value of the longest possible prefix of the string[p,L-1] which is also the prefix of the string[0,L-1].
In other words we can say that Z[p] calculates longest common prefix of the string[0,L-1] and the string [p,L-1].
In this question it was asked to calculate longest common prefix of the string [0,p-1] and string [p,L-1] (1<=p<=L-1).
For any query p, if length of first part(length of first part is p) is less than or equal to Z[p] then answer will always be equal to the length of the first part ie p.
If length of first part§ is greater than or equal to Z[p] then answer will always be equal to the value of Z[p].
Briefly, for any query, we get a index p as input then answer for that query will be:
ans = min( p , Z[p] ).
Complexity is O(N + Q) time. Construction of Z-array is in O(N) and each query is answered in O(1) time hence N+Q
For understanding Z-Algorithm refer this:
Z-Algorithm
Now we will see the solution using String Hashing + Binary Search.
Smallest possible answer for any query is 0. Largest possible answer for any query is min(Length of first part , Length of second part). So now we have a range and we need to find the best possible answer. We can achieve this efficiently using binary search. All we need to do is know to calculate in O(1) time whether a number given by our binary search( ie mid ) can be our answer or not. This can be achieved by Rolling Hash(Rabin-Karp).
In this method we calculate the answer of each query in logN time. So overall complexity of this code is Q*logN