ACM RTK - 2. skupina

Skrivno sporočilo

Si vohun sove, ki dela pod krinko in ravnokar si ,,opravil'' z agentom zlobne zločinske organizacije orel, ki je poskušal poslati podatke o času in kraju dostave pomembnega paketa svojim nadrejenim. Pri nakazovanju svoje superiornosti si bil malce pregrob, tako da agenta sedaj ne moreš izprašati, temveč nemočno držiš v rokah njegovo komunikacijsko napravo, kjer se na zaslonu bleščita sporočilo, ki ga je agent želel poslati, in njegova napol zašifrirana kopija. Tvoja želja je, da v njegovem imenu pošlješ svoje sporočilo, ki bo seveda vsebovalo napačen kraj in čas dostave, da boste lahko ne le varno prejeli paket, temveč tudi ujeli še kakšnega agenta.

Agenti orla svoja sporočila šifrirajo zelo primitivno, črke abecede le malo zamešajo med seboj in pišejo namesto a na primer r in podobno. Tvoja naloga je, da preveriš, ali je delno zašifrirano sporočilo veljavno, in čim bolj ugotoviš šifro ter na enak način, kolikor je le mogoče, zašifriraš svoje sporočilo. Zašifirano sporočilo je veljavno, če se enaki črki vedno zašifirirata v enaki črki, poleg tega pa se morata različni črki šifrirati v različni črki, da je sporočilo mogoče odkodirati. (Bolj matematično: kodirna funckcija mora biti bijektivna). Primera neveljavnih kodiranj sta cat → bgb in zoo → srt, primer veljavnega kodiranja pa je npr. please → rlagha.

Napiši podprogram (funkcijo) Desifriraj(p1, c1, p2), ki kot parametre dobi tri nize:

• p1 je originalno (nešifrirano) sporočilo.
• c1 je delno šifrirano sporočilo, ki smo ga zasegli sovražnemu agentu. Ta niz je enako dolg kot originalno sporočilo. V njem nastopajo že zašifrirane črke; na mestih, ki jih agent še ni utegnil zašifrirati, pa je namesto črke zvezdica (znak *).
• p2 je tvoje sporočilo, ki ga želiš zašifrirati po enakem postopku, kot ga je uporabil sovražni agent.

Vsa sporočila vsebujejo samo male črke angleške abecede in so krajša od 10.000 znakov. Tvoj podprogram naj izpiše zašifrirano različico tvojega sporočila p2 (če za nekatere znake ni mogoče zanesljivo ugotoviti, v kaj bi se morali zašifrirati, namesto njih izpiši zvezdico *); če pa dano šifrirano sporočilo ni veljavno, izpiši ,,neveljavna šifra''.

Primer: recimo, da dobimo nize

p1 = nexttuesdayfourfiftypminthemainsquare
c1 = r**aa**k***s****e***q*e**o********wl*
p2 = thistuesdayfourfiftypmanddefinetlynotnexttuesdayfourfiftypminthemainsquare

Pravilni izpis je potem takšen:

aoeka**k*w*s**lsesa*q*wr***ser*a**r*ar**aa**k*w*s**lsesa*q*erao**werk**wl*