QUERYSTR  Query Problem
McFn interesed in string problem recently.He found a interesing function and he felt he could use this function to invent a new match algorithm.
For a string S [1 ... n] and i ¡Ê [1, n], define F (i) is the length of the longest common suffix of S and S [1 ... i].
For example, for the string S [1 ... 11] = zaaxbaacbaa, then F (1) = 0, F (2) = 1, F (3) = 2 (note that S [1 ... 3] = zaa), F (4) = 0, ... ... F (10) = 1, F (11) = 11;
For the string S [1 ... n], i ¡Ê [1, n], S [i ... n] is its suffix;
Input
The first line is a integer T.the number of test cases
for each test case
The first line is a string S, composed of only lowercase letters, len (s) is the length of s, 1 <= len (s) <= 1000000;
Next line, a number N (1 <= N <= 100000), denote that the number of quiries;
The next N lines, each line contains a number x (1 <= x <= len (s)).
Output
For each x the output F (x);
Example
Input:
1
zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11
Output: 0
1
2
0
0
1
3
0
0
1
11
hide comments
aryan29:
20190915 08:46:32
standard Z algo on reversed string thats it 

rohijulislam:
20180512 12:49:37
Z algo 

sultania23:
20170719 15:11:43
good problem on this concept:


Antriksh Agarwal:
20170224 15:57:44
I don't understand just one thing. If I am matching S with S[i...n] how can F[11]=11 because S[11..11] is a single letter ? And, if we are checking S[1..i] with S, how can F[1]=0, because S[1..1] is a single letter present in S as S[1] ? Or the third case, when S[1..i] is checked with S[i..n], F[11]!=11, can never because on i=11, S[1..11] is checked with S[11...11] which is a single character. 

ashishranjan28:
20160916 07:33:03
use scanf and printf 

ravi shankar:
20160819 11:46:18
ac in one go ;) 

Rameshwar:
20160620 15:46:47
Used Z algorithm , getting TLE even with scanf.... Am I missing something in this problem? 

i_love_coding:
20160411 22:25:56
I am in Love with Strings..:P 

janina:
20160127 08:27:43
Z works well :) 

Sonu Sharma:
20150916 18:33:23
Large input size :) use fast i/o 
Added by:  Hemant Verma 
Date:  20091115 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Alkhwarizm 2009 