QUERYSTR - Query Problem

no tags 


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: 2019-09-15 08:46:32

standard Z algo on reversed string thats it

rohijulislam: 2018-05-12 12:49:37

Z algo

sultania23: 2017-07-19 15:11:43

good problem on this concept:-
http://codeforces.com/contest/825/problem/G

Last edit: 2017-07-19 15:11:58
Antriksh Agarwal: 2017-02-24 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: 2016-09-16 07:33:03

use scanf and printf

ravi shankar: 2016-08-19 11:46:18

ac in one go ;)

Rameshwar: 2016-06-20 15:46:47

Used Z algorithm , getting TLE even with scanf.... Am I missing something in this problem?

i_love_coding: 2016-04-11 22:25:56

I am in Love with Strings..:P

janina: 2016-01-27 08:27:43

Z works well :)

Sonu Sharma: 2015-09-16 18:33:23

Large input size :) use fast i/o


Added by:Hemant Verma
Date:2009-11-15
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