Maria vrea să îi trimită lui Radu un mesaj secret. Pentru a ascunde mesajul de prietena ei, Maria criptează mesajul folosind un algoritm simplu, care utilizează ca şi cheie un şir suplimentar. Mesajul şi cheia sunt şiruri de litere mici din alfabetul englez. Metoda de criptare cuprinde mai multe etape:
Cheia se repetă ciclic până când şirul rezultat este de aceeaşi lungime ca şi mesajul.
Fiecare literă atât din cheie cât şi din mesaj este reprezentată de un număr între 0 şi 25 (litera 'a' este numărul 0; 'b' este de 1, etc.).
Fiecare literă din mesaj se adaugă la litera corespunzătoare din cheie (prin adăugarea valorilor numerice). Dacă rezultatul este 26 sau mai mult, Maria scade 26 din acesta pentru a obţine o valoare între 0 şi 25.
Rezultatul final este reprezentat ca un şir de litere (0 pentru 'a', 1 pentru 'b' etc.)
De exemplu, dacă vom cripta mesajul "bunadimineata" cu cheia "abz", vom obţine rezultatul "bvmaehmjmebsa": a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
b u n a d i m i n e a t a 1 20 13 0 3 8 12 8 13 4 0 19 0
a b z a b z a b z a b z a 0 1 25 0 1 25 0 1 25 0 1 25 0
---------------------------------------------------------------------
b v m a e h m j m e b s a 1 21 12 0 4 7 12 9 12 4 1 18 0
Din păcate, prietena Mariei a descoperit metoda de criptare. Chiar dacă ea nu ştie cheia, ea cunoaşte o parte a mesajului original, deoarece l-a auzit. Această parte a mesajului are lungimea cel puţin de două ori mai mare decât lungimea cheii, şi apare în mesaj cel puţin o dată, dar prietena Mariei nu ştie unde.
Cerinţă
Scrieţi un program care, cunoscând mesajul criptat şi partea cunoscută a mesajului original, determină mesajul original.
Date de intrare
Prima linie a fişierului de intrare cheie.in conţine mesajul criptat, un şir de cel mult 1000 litere mici (fără spaţii). A doua linie a fişierului de intrare conţine partea auzită a mesajului, un şir de cel mult 200 litere mici (fără spaţii).
Date de ieşire
Fişierul de ieşire cheie.out va conţine pe prima linie mesajul decodificat, terminat cu caracterul sfârşit de linie.
Restricţii
mesajul criptat, cheia, segmentul auzit şi mesajul decodificat conţin numai caractere mici ale alfabetului
pentru datele de intrare există soluţie unică
se va utiliza pentru decodificare cheia de lungime maximă posibilă
lungimea minimă a cheii este 2 şi maxim 100 caractere
lungimea mesajului criptat este maxim 1000 caractere.
Exemplu
cheie.in
cheie.out
Explicaţii
psinattfa
mast
primastea
Obsevăm că prin poziţionarea secvenţei auzite mast sub mesajul criptat începând de la poziţia 4, avem configuraţia
psinattfa
mast
De aici se poate deduce faptul că, pentru cheie de forma 'xy', de lungime 2 (maximă posibil în acest caz) 'm' + x = 'n' şi 'a' + y = 'a', deci posibila cheie ar fi x = 1, y = 0, adică 'ba'. Acest lucru este validat de perechea următoare de relaţii 's' + x = 't' şi 't' + y = 't'.