Module: Fungsi awalan, fungsi Z


Problem

5 /10


fungsi Z

Theory Click to read/hide

Z-function
Z-function daripada rentetan S - tatasusunan Z, setiap elemen ialah Z [i ] adalah sama dengan awalan terpanjang subrentetan bermula pada kedudukan i dalam rentetan S, yang juga merupakan awalan keseluruhan rentetan Z. Nilai fungsi Z-pada kedudukan sifar biasanya sama ada sifar atau panjang keseluruhan rentetan.
Kesukaran
O(|S| ^ 2) atau O(|S|).
 
Fungsi awalan daripada rentetan S - tatasusunan P, setiap elemen yang P[i] adalah sama dengan akhiran terpanjang bagi subrentetan bermula dari kedudukan < code>i dalam rentetan S, yang juga merupakan akhiran keseluruhan rentetan S. Nilai P-fungsi pada kedudukan sifar biasanya sama ada sifar atau panjang keseluruhan rentetan. 
Kesukaran
O(|S| ^ 2) atau O(|S|).
 
Cuba laksanakan Fungsi Z dan fungsi awalan untuk O(|S| ^ 2) .

Problem

Dua rentetan diberikan - S dan T. Tugas anda ialah untuk memaparkan bilangan kejadian awalan i-th rentetan S dalam rentetan T.

Input
Baris pertama mengandungi k - bilangan pertanyaan (\(k <= length( S)\)), rentetan S< /code> dan rentetan T. Seterusnya, permintaan k dimasukkan, permintaan untuk bilangan kejadian awalan i-ke rentetan S dalam rentetan T.

Output
Output k baris respons pertanyaan.

 

Contoh

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!

# Input Output
1
2 ali balimali
3
0
 2
8