Strings And Queries

5

1 votes
Binary Search, Z-algorithm, Medium, Sqrt-Decomposition, Hashing
Problem

You are given 2 strings text and pattern, consisting of lowercase english letters. 

Let str be any substring of pattern having some length len greater than 0. Then the starting index of each occurence, if any, of str in text is contained in the set S(len).

You have to answer multiple queries. For each query, you need to determine the Kth samllest element among all the elements in S(L), S(L+1),......, S(R-1), S(R) (duplicates, if any, are retained). If the answer is not possible, then print -1.

Note: 

  • The indexing of text begins from 0.
  • S(i) is a set (i.e. it contains only distinct elements).
     

Input Format:

The first line contains the string text. (1 ≤ |text| ≤ 10^5)

The second line contains the string pattern. (1 ≤ |pattern| ≤ 10^3)

The third line contains an integer denoting the number of queries, Q. (1 ≤ ≤ 10^5)

Then follow lines.

Each of the Q lines contains 3 integers L, R and K. (1 ≤ L ≤ R ≤ |pattern|, 1 ≤ ≤ 10^8)

 

Output Format:

For each query, output the Kth smallest element is S(L),S(L+1),....,S(R-1),S(R).

If the answer is not possible, then output -1.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

S(1) = {0,1,2,3,4,5}
S(2) = {0,1,2,3}
S(3) = {0,1,2}
S(4) = {0,1}
S(5) = {0}

Query 1: S(1),S(2) = {0,0,1,1,2,2,3,3,4,5}
The 7th smallest element is 3.

Query 2: S(2),S(3),S(4),S(5) = {0,0,0,0,1,1,1,2,2,3}
There are only 10 elements. So the output is -1.

Query 3: S(2),S(3),S(4),S(5) = {0,0,0,0,1,1,1,2,2,3}
The 9th smallest element is 2.

Editor Image

?