All submissions for this problem are available.There is a vast amount of text data in the Universe. There is a search engine Gnib which searches the entire text of the Universe but the problem is this search engine is not as good as Google. Now, Morty wants to query a string to find it in the text. There is an integer parameter $X$ associated with every query which is decided by the search engine Gnib. You are given $Q$ queries each containing a string $S$ and an integer $X$. Now, the search engine will only show results if the number of results is less than or equal to $X$. Morty will type the query string character by character and the search engine will look for the number of distinct substrings in the text which share the same prefix as that of the query string. If that number is less than the parameter $X$, it will display all the distinct substrings whose prefix matches the currently entered query string. Your task is to find the minimum index in the query string when the results will be displayed. Note: 1.) It is guaranteed that all the query strings are some substring of the text. 2.) If the query string finishes, but still the search predictions cannot be narrowed down to less than or equal to $X$, print -1. 3.) Assume 1-based indexing. ###Input: - First-line will contain a string $Text$ of length $N$ on which queries will be made. - Second-line will contain $Q$ (number of queries) - Third line will contain $Q$ strings separated by space. - Fourth line will contain $Q$ integers denoting the parameter of the query string. ###Output: - Print the output for all the Q queries space separated in a single line. ###Constraints - $1 \leq |Text| \leq 10^5$ - $1 \leq |S| \leq 10^5$ - Summation of length of all query strings is less than $5 * 10^5$ - $1 \leq |X| < Number of distinct substring of Text$ ###Sample Input: AAAA 2 AA AAA 3 1 ###Sample Output: 2 -1 ###EXPLANATION: when we enter the first character, there can be 4 predicted outputs, after entering the 2nd character, the no. of possible predictions reduces to 3 which is within display limit hence answer is 2. in the second query, even after entering the complete string the no. of options remain 2, hence its more than the limit, therfore -1 is printed
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.