The Gift Of Raksha Bandhan
All submissions for this problem are available.
Its time of Raksha Bandhan so its compulsory for every
brother to give a gift to his sister.
Brother Jon is planning to give a string S of length
L to his sister Arya.
After receiving the gift from her brother, Arya decided to share
the string with her brother Jon.
String S contains characters from index 0 to
index L - 1.
She will select a pivot called P ie any index P(1 ≤ P ≤ L - 1) and divides the original string into two parts. First
part will contain characters from index 0 to index P - 1 and second part will contain characters from index
P to L - 1.
Jon will keep the first part and Arya will keep the second
Arya is great fan of LCP (Longest Common Prefix) so she
decided that she will select such an index as pivot such that
LCP of the two part is high.
Though she like LCP but she does not know how to calculate
it. Help her to solve the problem.
Arya will ask you Q questions. Each question is
represented by a index P and you have to answer the LCP
(Longest Common Prefix) of the two parts.
First line of input contains a string S.
Second line of input contains a positive number Q
representing the number of question Arya will ask you.
Q lines will follow each containing a positive
Output Q numbers(the required answer). Each number
on a separate line.
- 1 ≤ Length of the string(or L) ≤
5 * 106
- 1 ≤ P ≤ L - 1
- 1 ≤ Q(number of queries) ≤ 106
- All characters in the string will be small case english alphabets (a-z)
NOTE: C++ users, please do not use cin and cout as test cases are huge, prefer scanf and printf
Input: abababa 4 1 2 3 6 Output: 0 2 0 1
For the first query, first part is a.and second part is bababa, hence LCP is 0.
For the second query, first part is ab.and second part is ababa, hence LCP is 2.
For the third query, first part is aba.and second part is baba, hence LCP is 0.
For the fourth query, first part is ababab.and second part is a, hence LCP is 1.
|Tags||amanmittal, binary-search, hashing, insq2015, rabin-karp, z-algorithm|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.