Module: Funzione prefisso, funzione Z


Problem

10 /10


Cifra

Theory Click to read/hide

 
Sia Z che il prefisso della funzione possono essere usati per implementare l'algoritmo KMP(Knuth-Morris-Pratt) per trovare una sottostringa in una stringa in O(|S|). L'essenza di questo algoritmo è la seguente: attribuiamo alla stringa che vogliamo trovare la stringa in cui stiamo cercando. È altamente desiderabile inserire un carattere separatore tra queste righe, ovvero un carattere che non ricorre in nessuna riga (di solito #).

Problem

Corwin è stato in grado di intercettare n messaggi sui movimenti delle truppe di Eric. È vero, si sono rivelati crittografati, ma non importa! Lo aiuterai a decifrare questi messaggi? Questo non dovrebbe essere difficile, poiché Corwin conosce almeno una sottostringa in ogni messaggio originale.

Per la cifratura, Eric usa un cifrario di Cesare, cioè un cifrario in cui la lettera con il numero i è sostituita dalla lettera con il numero i + k , dove k è un numero.

Poiché i compilatori moderni non supportano l'alfabeto ambra, sostituiremo i caratteri con il loro numero di serie - un numero da 1 a q, dove < code> q - il numero di caratteri dell'alfabeto.

Ogni messaggio è lungo x e ogni sottostringa nota della sua decrittazione è y.

Il tuo obiettivo è ripristinare tutti i messaggi originali.

IL FORNITORE CON STD::STRING ANDRÀ NEI CANTIERI DEL CAOS!!!
 
Input
La prima riga legge i numeri n (\(1 <= n <= 100\)) e q < /code> (\(1 <= k <= 100\))
Le seguenti righe 3 * n contengono i numeri xi, yi (\(1 <= b_i <= a_i <= 100\)) e 2 array di numeri che rappresentano il messaggio e la sua sottostringa di decrittazione.

Impressum
Nella riga numero i stampa la versione decodificata del messaggio con il numero i.
Ci deve essere NON DEVE alla fine di questa riga


Esempi
# Input Uscita
1 1 11
10 4
11 7 1 1 2 6 7 1 1 8
2778 		6 2 7 7 8 1 2 7 7 3

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!