[ONI][IX]Criptare

Mircea si Vasilica vor sa-si trimita mesaje pe care altii sa nu le inteleaga. Au citit ei despre spioni si modalitati de a scrie mesaje si, in final, au imaginat un mod de criptare a unui mesaj care foloseste “cuvant cheie” (le-a placut lor denumirea asta 🙂 ).

Alegandu-si un cuvant cheie format numai din litere distincte, ei numara literele acestuia si impart mesajul in grupe de lungime egala cu numarul de litere ale cuvantului cheie, si le aseaza una sub alta. Desigur, se poate intampla ca ultima grupa sa fie incompleta, asa ca o completeaza cu spatii. Apoi numeroteaza literele cuvantului cheie in ordinea aparitiei lor in alfabetul englez. In final, rescriu mesajul astfel: coloana de sub litera numerotata cu 1, urmata de coloana de sub litera numerotata cu 2, etc. inlocuind totodata si spatiile cu caracterul ‘*’ (asterisc).

Exemplu:

        cuvantul cheie             criptam
        mesaj de criptat           Incercam sa lucram cu coduri si criptari.
cuvantul cheie                     criptam are 7 litere
numerotare                         2635714
deoarece, avem, in ordine      abcdefghijklmnopqrstuvwxzy
			              	     1  2       3   4   5  6 7
impartire in grupe                  Incerca|m sa lu|cram cu| coduri| si cri|ptari.
codificare                               2635714
                                         Incerca
                                         m*sa*lu
                                         cram*cu
                                         *coduri
                                         *si*cri
                                         ptari.*
mesaj criptat                       clcrr.Imc**pcsaoiaauuii*eamd*rn*rcstr**uci
                                         col1  col2   col3    col4    col5    col6    col7

Cerinta
Fiind date un cuvant cheie si un mesaj criptat, decodificati mesajul trimis de Mircea pentru Vasilica.

Date de intrare
Fisierul de intrare criptare.in contine pe prima linie mesajul criptat iar pe linia a doua cuvantul cheie.

Date de iesire
Fisierul de intrare criptare.out contine pe prima linie mesajul decriptat.

Restrictii
• lungimea mesajului este de minim 20 si maxim 1000 caractere
• cuvantul cheie are minim 5 si maxim 20 de caractere
• cuvantul cheie contine numai litere mici ale alfabetului

Exemplu
criptare.in

clcrr.Imc**pcsaoiaauuii*eamd*rn*rcstr**uci
criptam

criptare.out

Incercam sa lucram cu coduri si criptari.

Timp maxim de executie/test: 1 secunda

Solutie :
Timp executie :
O(keyLen ^ 2) – pentru generarea cheiei
O(keyLen ^ 2+msgLen/keyLen) – pentru decriptare
Memorie folosita : O(msgLen + 2 keyLen)

Dupa parerea mea problema nu este dificila doar este foarte interesanta.
Avem nevoie de o funcție ce va genera cheia.Funcția decriptHash este funcția de baza pentru decriptare.Ea simuleaza imparțirea stringului in sub-stringuri de lungimea cheii si face decriptarea direct.

Soluție : Problema Criptare