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
aryan29:
2019-09-15 08:46:32
standard Z algo on reversed string thats it |
|
rohijulislam:
2018-05-12 12:49:37
Z algo |
|
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 |
|
Abhilash:
2015-09-07 09:25:46
precomputing works! |
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 |