QUERYSTR - Query Problem
McFn interested in string problem recently. He found a interesting 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 queries;
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
Stupid Dog:
2015-07-10 12:11:39
C++ : getline(cin,s) : WA ; cin >> s : AC |
|
THECOLDONE:
2015-06-29 11:21:00
i think test case are right ,easy one |
|
Rishav Goyal:
2013-06-23 11:38:20
@hemant, i think there is problem with testcases !!
|
|
Rishav Goyal:
2013-06-23 11:37:21
i don understand,i am doing in log(N), still tle !!
|
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 |