PROBLEM LINK:
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.