Module: Fonction préfixe, fonction Z


Problem

10 /10


Chiffrer

Theory Click to read/hide

 
Z et le préfixe de la fonction peuvent être utilisés pour implémenter l'algorithme KMP(Knuth-Morris-Pratt) pour trouver une sous-chaîne dans une chaîne en O(|S|). L'essence de cet algorithme est la suivante : nous attribuons à la chaîne que nous voulons trouver la chaîne dans laquelle nous recherchons. Il est fortement souhaitable de mettre un caractère séparateur entre ces lignes, c'est-à-dire un caractère qui n'apparaît sur aucune ligne (généralement #).

Problem

Corwin a pu intercepter n messages sur les mouvements de troupes d'Eric. Certes, ils se sont avérés cryptés, mais peu importe ! Allez-vous l'aider à déchiffrer ces messages ? Cela ne devrait pas être difficile, car Corwin connaît au moins une sous-chaîne dans chaque message d'origine.

Pour le chiffrement, Eric est connu pour utiliser un chiffrement de César, c'est-à-dire un chiffrement dans lequel la lettre avec le chiffre i est remplacée par la lettre avec le chiffre i + k , où k est un certain nombre.

Étant donné que les compilateurs modernes ne prennent pas en charge l'alphabet Ambre, nous remplacerons les caractères par leur numéro de série - un nombre compris entre 1 et q, où < code> q - le nombre de caractères dans l'alphabet.

Chaque message est long de x, et chaque sous-chaîne connue de son déchiffrement est y.

Votre objectif est de restaurer tous les messages d'origine.

LE FOURNISSEUR AVEC STD ::STRING VA DANS LES CHANTIERS DU CHAOS !!!
 
Entrée
La première ligne lit les nombres n (\(1 <= n <= 100\)) et q < /code> (\(1 <= k <= 100\))
Les lignes 3 * n suivantes contiennent des nombres xi, yi (\(1 <= b_i <= a_i <= 100\)) et 2 tableaux de nombres représentant le message et sa sous-chaîne de déchiffrement.

Mentions légales
Dans la ligne numéro i imprimer la version décodée du message avec le numéro i.
Il doit y avoir NE DOIT PAS à la fin de cette ligne


Exemples
# Entrée Sortie
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

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!