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
part.
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.
Input
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
number P
Output
Output Q numbers(the required answer). Each number
on a separate line.
Constraints
 1 ≤ Length of the string(or L) ≤
5 * 10^{6}
 1 ≤ P ≤ L  1
 1 ≤ Q(number of queries) ≤ 10^{6}
 All characters in the string will be small case english alphabets (az)
NOTE: C++ users, please do not use cin and cout as test cases are huge, prefer scanf and printf
Example
Input: abababa 4 1 2 3 6 Output: 0 2 0 1
Explanation
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.
Author:  amanmittal 
Editorial  http://discuss.codechef.com/problems/INSQ15_A 
Tags  amanmittal, binarysearch, hashing, insq2015, rabinkarp, zalgorithm 
Date Added:  2092015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 