INSQ16F - Editorial

PROBLEM LINK:

Practice

Contest

Author: Vikash Kumar Dubey

Tester: Vipin Singh

Editorialist: Vipin Singh

DIFFICULTY:

Medium

PREREQUISITES:

Strings,Suffix Array

PROBLEM:

Given N no of strings and Q queries of the form i,j.Find the LCP of strings at ith and jth index,let us call it X.Then find the no of occurences of X as a substring in the given input strings.

QUICK EXPLANATION:

Build a suffix array over the concatenation of the all strings and use binary search to find the answer.

EXPLANATION:

Let us build a string , all = s1 + ‘#’ + s2 +… + ‘#’ + sn.Where Si is the ith input string.Build the Suffix array over this string , let us call it SA.

How to answer each query?

Let i and j be the given indexes for a particular query.First find the position of the si and sj in the suffix array.We could easily do it using a hashmap over the suffix array.

Let these indexes be ft and st (assuming ft < st without the loss of generality) and the LCP of these two strings be lcp.

It can be observed that for all indexes k between 0 and ft , LCP(k,ft) will be an increasing function , also for all indexes k between st and n , LCP(k,st) wiil also be an increasing function.

So we will use binary search to find two indexes :

First index is leftmost which is the minimum index betwen 0 and ft , such that LCP(leftmost,ft)>=k.

Second index is rightmost which is the maximum index between st and (n-1), such that LCP(rightmost,st)>=k

The answer to the problem is (rightmost-leftmost+1)

Solution

Tester’s solution can be found here.

1 Like

I solved this problem using some pre-processing(next lesser element for each index of the lcp array). But I don’t understand the following observation:

It can be observed that for all indexes k between 0 and ft , LCP(k,ft) will be an increasing function , also for all indexes k between st and n , LCP(k,st) wiil also be an increasing function.