INSQ15_A - Editorial

general
, , , ,
1

The Gift Of Raksha Bandhan

PROBLEM LINK

Practice

Contest

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(p) 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

1 Like
2

can anyone elaborate on how to approach the problem through string hashing and binary search?Didn’t quite understand it…
Does the editorial mean something lik this??
hash1[] = hash of string 1
hash2[] = hash of string 2
lo = 0
hi = length of shorter string + 1
mid = (lo + hi) / 2
if (common substring of length == mid):
lo = mid
else
hi = mid
But that would take q*logn^2?? plz help anyone?? ):

3

You can refer to this.

Rabin-Karp + Binary Search solution:

  1. Compute hash for every prefix of the string in O(N) total.
  2. Now, we’ll do a binary search on all possible lengths: 0 to min(P, N-P), to find the highest value, say, mid , where
    substring [0 to mid] = substring [P to P+mid]

  1. Each time, we can do this checking in O(1), and we’ll have to check O(logN) times per query Q, to find the highest length.

  2. Thus overall complexity is O(N+QlogN).

1 Like
4

Can we do this ques using KMP algo ? If yes , How ?

6

I don’t think there is a way to solve this using KMP, given the constraints

7

Why my

submission

is giving me wrong answer. Can anyone provide any counter test case pls.