Module: Prefix function, Z function


Problem

5 /10


Z function

Theory Click to read/hide

Z-function
Z-function from string S - array Z, each element of which is Z[i ] is equal to the longest prefix of the substring starting at position i in the string S, which is also the prefix of the entire string Z. The value of the Z-function at position zero is usually either zero or the length of the entire string.
Difficulty
O(|S| ^ 2) or O(|S|).
 
Prefix function from the string S - array P, each element of which P[i] is equal to the longest suffix of the substring starting from position < code>i in the string S, which is also the suffix of the entire string S. The value of the P-function at position zero is usually either zero or the length of the entire string. 
Difficulty
O(|S| ^ 2) or O(|S|).
 
Try to implement Z function and prefix function for O(|S| ^ 2).

Problem

Two strings are given - S and T. Your task is to display the number of occurrences of the i-th prefix of the string S in the string T.

Input
The first line contains k - the number of queries (\(k <= length( S)\)), string S< /code> and the string T. Next, k requests are entered, a request for the number of occurrences of the i-th prefix of the string S in the string T.

Output
Output k lines of query responses.

 

Examples
# Input Output
1
2 ali balimali
3
0
 2
8

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!