ACM RTK - 2. skupina

Dekodiranje nizov

Dan je naslednji postopek za kodiranje besedila (niza znakov):

• Niz začnemo brati od začetka, dokler ne pridemo do prvega samoglasnika. Nato vse prebrane znake, vključno s tistim samoglasnikom, napišemo v obratnem vrstnem redu. Ob tem si shranimo podatek, koliko znakov smo zamenjali pri tej prvi menjavi.
• Sedaj preberemo vse znake od prvega samoglasnika dalje (toda brez tega samo- glasnika), dokler ne pridemo do drugega samoglasnika. Zopet vse prebrane znake, vključno z drugim samoglasnikom, napišemo v obratnem vrstnem redu. S tem je drugi samoglasnik prišel na drugo mesto v nizu, takoj za prvim samoglasnikom. Shranimo podatek, koliko znakov smo zamenjali pri tej drugi menjavi.
• Postopek ponavljamo, dokler ne pridemo do konca besedila.

Primer: oglejmo si postopek kodiranja niza ”SOBA Z RAZGLEDOM NA VRT“. Za samoglasnike štejejo znaki A, E, I, O in U. V vsaki vrstici je podčrtan tisti del niza, ki ga bomo v tem koraku obrnili; številka na desni pa je dolžina tega dela.

SOBA Z RAZGLEDOM NA VRT    (2)
OSBA Z RAZGLEDOM NA VRT    (3)
OABS Z RAZGLEDOM NA VRT    (7)
OAAR Z SBZGLEDOM NA VRT   (10)
OAAELGZBS Z RDOM NA VRT   (11)
OAAEODR Z SBZGLM NA VRT   (14)
OAAEOAN MLGZBS Z RD VRT

Opiši postopek za dekodiranje tako zakodiranega niza. Postopek torej kot vhodne podatke dobi kodirani niz (v zgornjem primeru: OAAEOAN MLGZBS Z RD VRT) in seznam s številom zamenjanih znakov pri vsaki menjavi (v zgornjem primeru: 2, 3, 7, 10, 11, 14). Predpostavi, da niz vsebuje le velike črke angleške abecede (od A do Z) in presledke.

Dekodiranje za zgornji primer:

(14) OAAEOAN MLGZBS Z RD VRT
(11) OAAEODR Z SBZGLM NA VRT
(10) OAAELGZBS Z RDOM NA VRT
(7)  OAAR Z SBZGLEDOM NA VRT
(3)  OABS Z RAZGLEDOM NA VRT
(2)  OSBA Z RAZGLEDOM NA VRT
     SOBA Z RAZGLEDOM NA VRT