[Solution] Prefix Function Queries solution codeforces

Table of Contents

Prefix Function Queries solution codeforces

Prefix Function Queries solution codeforces – You are given a string 𝑠s, consisting of lowercase Latin letters.

You are asked 𝑞q queries about it: given another string 𝑡t, consisting of lowercase Latin letters, perform the following steps:

  1. concatenate 𝑠s and 𝑡t;
  2. calculate the prefix function of the resulting string 𝑠+𝑡s+t;
  3. print the values of the prefix function on positions |𝑠|+1,|𝑠|+2,,|𝑠|+|𝑡||s|+1,|s|+2,…,|s|+|t| (|𝑠||s| and |𝑡||t| denote the lengths of strings 𝑠s and 𝑡t, respectively);
  4. revert the string back to 𝑠s.

Prefix Function Queries solution codeforces

The prefix function of a string 𝑎a is a sequence 𝑝1,𝑝2,,𝑝|𝑎|p1,p2,…,p|a|, where 𝑝𝑖pi is the maximum value of 𝑘k such that 𝑘<𝑖k<i and 𝑎[1..𝑘]=𝑎[𝑖𝑘+1..𝑖]a[1..k]=a[i−k+1..i] (𝑎[𝑙..𝑟]a[l..r] denotes a contiguous substring of a string 𝑎a from a position 𝑙l to a position 𝑟r, inclusive). In other words, it’s the longest proper prefix of the string 𝑎[1..𝑖]a[1..i] that is equal to its suffix of the same length.

Input

The first line contains a non-empty string 𝑠s (1|𝑠|1061≤|s|≤106), consisting of lowercase Latin letters.

The second line contains a single integer 𝑞q (1𝑞1051≤q≤105) — the number of queries.

Each of the next 𝑞q lines contains a query: a non-empty string 𝑡t (1|𝑡|101≤|t|≤10), consisting of lowercase Latin letters.

Prefix Function Queries solution codeforces

For each query, print the values of the prefix function of a string 𝑠+𝑡s+t on positions |𝑠|+1,|𝑠|+2,,|𝑠|+|𝑡||s|+1,|s|+2,…,|s|+|t|.

Examples
input

Copy
aba
6
caba
aba
bababa
aaaa
b
forces
output

Copy
0 1 2 3 
1 2 3 
2 3 4 5 6 7 
1 1 1 1 
2 
0 0 0 0 0 0 

Prefix Function Queries solution codeforces

input

Copy
aacba
4
aaca
cbbb
aab
ccaca
output

Copy
2 2 3 1 
0 0 0 0 
2 2 0 
0 0 1 0 1 

 

For Solution

“Click Here”

Leave a Comment