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


Problem

10 /10


mật mã

Theory Click to read/hide

 
Cả Z và tiền tố hàm đều có thể được sử dụng để triển khai thuật toán KMP(Knuth-Morris-Pratt) để tìm một chuỗi con trong một chuỗi trong O(|S|). Bản chất của thuật toán này như sau: chúng tôi gán cho chuỗi mà chúng tôi muốn tìm chuỗi mà chúng tôi đang tìm kiếm. Bạn nên đặt một ký tự phân cách giữa các dòng này, tức là một ký tự không xuất hiện trong bất kỳ dòng nào (thường là #).

Problem

Corwin có thể chặn n tin nhắn về việc di chuyển quân của Eric. Đúng, hóa ra chúng đã được mã hóa, nhưng điều đó không thành vấn đề! Bạn sẽ giúp anh ấy giải mã những thông điệp này chứ? Điều này không khó vì Corwin biết ít nhất một chuỗi con trong mọi thư gốc.

Để mã hóa, Eric được biết là sử dụng mật mã Caesar, tức là mật mã trong đó chữ cái có số i được thay thế bằng chữ cái có số i + k , trong đó k là một số.

Vì các trình biên dịch hiện đại không hỗ trợ bảng chữ cái Màu hổ phách nên chúng tôi sẽ thay thế các ký tự bằng số sê-ri của chúng - một số từ 1 đến q, trong đó < code> q - số ký tự trong bảng chữ cái.

Mỗi tin nhắn dài x và mỗi chuỗi con đã biết của quá trình giải mã của nó là y.

Mục tiêu của bạn là khôi phục tất cả thư gốc.

NGƯỜI CUNG CẤP CÓ STD::STRING SẼ CHUYỂN ĐẾN MỨC TỔN THƯƠNG!!!
 
Đầu vào
Dòng đầu tiên ghi số n (\(1 <= n <= 100\)) và q < /code> (\(1 <= k <= 100\))
Các dòng 3 * n sau chứa các số xi, yi (\(1 <= b_i <= a_i <= 100\)) và 2 dãy số đại diện cho tin nhắn và chuỗi con giải mã của nó.

Dấu ấn
Trong dòng số i in phiên bản đã giải mã của tin nhắn với số i.
Phải có MUST NOT ở cuối dòng này


Ví dụ
<đầu>

time 250 ms
memory 16 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 1 11
10 4
11 7 1 1 2 6 7 1 1 8
2 7 7 8 		6 2 7 7 8 1 2 7 7 3