Module: Chức năng tiền tố, chức năng Z


Problem

5 /10


chức năng Z

Theory Click to read/hide

Z-chức năng
Z-function từ chuỗi S - mảng Z, mỗi phần tử của nó là Z [i ] bằng tiền tố dài nhất của chuỗi con bắt đầu từ vị trí i trong chuỗi S, cũng là tiền tố của toàn bộ chuỗi Z. Giá trị của hàm Z tại vị trí 0 thường bằng 0 hoặc bằng độ dài của toàn bộ chuỗi.
Khó khăn
O(|S| ^ 2) hoặc O(|S|).
 
Hàm tiền tố từ chuỗi S - mảng P, mỗi phần tử trong đó P[i] bằng với hậu tố dài nhất của chuỗi con bắt đầu từ vị trí < code>i trong chuỗi S, cũng là hậu tố của toàn bộ chuỗi S. Giá trị của hàm P tại vị trí 0 thường bằng 0 hoặc bằng độ dài của toàn bộ chuỗi. 
Khó khăn
O(|S| ^ 2) hoặc O(|S|).
 
Thử triển khai hàm Z và hàm tiền tố cho O(|S| ^ 2) .

Problem

Có hai chuỗi - S và T. Nhiệm vụ của bạn là hiển thị số lần xuất hiện của tiền tố thứ i của chuỗi S trong chuỗi T.

Đầu vào
Dòng đầu tiên chứa k - số lượng truy vấn (\(k <= length( S)\)), chuỗi S và chuỗi T. Tiếp theo, yêu cầu k được nhập vào, yêu cầu về số lần xuất hiện của tiền tố thứ i của chuỗi S trong chuỗi T.

Đầu ra
Xuất k dòng câu trả lời truy vấn.

 

Ví dụ
<đầu>

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!

# Đầu vào Đầu ra
1
2 ali balimali
3
0
 2
8