Module: Fungsi awalan, fungsi Z


Problem

10 /10


Sifir

Theory Click to read/hide

 
Kedua-dua Z dan awalan fungsi boleh digunakan untuk melaksanakan algoritma KMP(Knuth-Morris-Pratt) untuk mencari subrentetan dalam rentetan dalam O(|S|). Intipati algoritma ini adalah seperti berikut: kami mengaitkan kepada rentetan yang kami mahu mencari rentetan yang kami cari. Adalah sangat diingini untuk meletakkan aksara pemisah antara baris ini, iaitu aksara yang tidak berlaku dalam mana-mana baris (biasanya #).

Problem

Corwin dapat memintas n mesej tentang pergerakan tentera Eric. Benar, mereka ternyata disulitkan, tetapi tidak mengapa! Adakah anda akan membantu dia menguraikan mesej ini? Ini tidak sepatutnya sukar, kerana Corwin mengetahui sekurang-kurangnya satu subrentetan dalam setiap mesej asal.

Untuk penyulitan, Eric diketahui menggunakan sifir Caesar, iaitu sifir di mana huruf dengan nombor i digantikan dengan huruf dengan nombor i + k , dengan k ialah beberapa nombor.

Memandangkan penyusun moden tidak menyokong abjad Amber, kami akan menggantikan aksara dengan nombor siri mereka - nombor daripada 1 hingga q, di mana < kod> q - bilangan aksara dalam abjad.

Setiap mesej adalah x panjang dan setiap subrentetan yang diketahui penyahsulitannya ialah y.

Matlamat anda adalah untuk memulihkan semua mesej asal.

PEMBEKAL DENGAN STD::STRING AKAN MENUJU KEKERAPAN!!!
 
Input
Baris pertama membaca nombor n (\(1 <= n <= 100\)) dan q < /code> (\(1 <= k <= 100\))
Barisan 3 * n berikut mengandungi nombor xi, yi (\(1 <= b_i <= a_i <= 100\)) dan 2 tatasusunan nombor yang mewakili mesej dan subrentetan penyahsulitannya.

Cetakan
Dalam nombor baris i cetak versi mesej yang dinyahkod dengan nombor i.
Mesti ada BOLEH di hujung baris ini


Contoh

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!

# Input Output
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