HAGU - Alia and Substrings
Alia wants to play with you. She will give you a string (MSG) where ((N = length of MSG) <= 10000) and multiple queries(M). Each query consists of an integer value K.
For each query you have to find the Kth substring if all the substrings of the given string are arranged in lexicographically increasing order without any duplicates (no substring will appear twice in the given arrangement). You have to output the starting index of the Kth substring and its size. If the found substring has duplicates then (substring occurs multiple times in the given string), output the smallest index where it occurs.
If the number of substring in the arrangement is less than the value of K, output -1.
Constraints
1 <= size of string(MSG) <= 10000
1 <= number of queries (M) <= 100000
1 <= K <= total number of substrings (not necessarily unique) of MSG;
Note: you have to output indexes as 1-based.
Input
The first line of input will consist of your string and number of queries (M), separated by a space. Next M lines will consist of integer K (as mentioned in the problem).
Output
Your output should consist of M lines as per the answer for each query.
Example
Input: aaaaa 3 1 2 3 Output: 1 1 1 2 1 3
Explanation:
Our arrangement here will consist of substrings in the following order (a), (aa), (aaa), (aaaa), (aaaaa)
So 1st substring will be "a" and it's occuring at multiple index - (1, 2, 3, 4, 5) out of which the smallest index is 1 and it's size is 1. Hence the answer will be (1, 1).
The same will be for the other two queries.
hide comments
|
Buda IM (retired):
2015-03-21 01:04:26
SUBLEX is similar question |
|
fitcat:
2014-10-23 07:41:02
My AC solution assumed all the characters in the string were in lower case. |
Added by: | pranjuldb |
Date: | 2014-09-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Codehurdle |