sms

T9 este un sistem dezvoltat pentru a satisface nevoia de a trimite cât mai rapid mesaje text (SMS) utilizând telefoane mobile. Un mesaj text consta dintr-o succesiune de cuvinte terminate prin câte un spatiu. Sistemul T9 este bazat pe un dictionar stocat în memoria telefonului. Daca utilizam acest sistem, atunci când tastam un cuvânt este suficient sa apasam pentru fiecare litera o singura tasta. La actionarea unei taste este afisat primul cuvânt din dictionar care contine, pe pozitia respectiva, una dintre literele înscrise pe tasta actionata. Cuvântul (daca exista în dictionar) va fi format luând literele de pe pozitiile corespunzatoare din fiecare cuvânt afisat, în ordine.

Exemplu (vezi exemplul 2)
Secventa de taste 2 9 4 duce la aparitia cuvintelor
2 AZI  (adica una dintre literele ABC pe prima pozitie)
9 AZI (adica una dintre literele WXZY pe pozitia a doua)
4 AZI (adica una dintre literele GHI pe pozitia a treia)
deci cuvântul format va fi AZI.

Fiecare litera a unui cuvânt care nu este în dictionar va fi înlocuita cu un caracter *. Daca exista mai multe cuvinte care corespund unei anumite secvente de actionari de taste, va fi afisat primul în ordine alfabetica.

Aranjarea literelor pe tastatura telefonului mobil este urmatoarea:

Cerinta

Scrieti un program care sa simuleze sistemul T9 pe baza unui dictionar dat.

Date de intrare

Fisierul de intrare sms.in contine:

Date de iesire

Fisierul de iesire sms.out contine pe o singura linie mesajul generat de sistemul T9 în urma apasarii celor N taste. Mesajul se termina cu caracterul spatiu urmat de sfârsit de linie.

Restrictii

1 <= M <= 100
Cuvintele C₁, C₂, ... , C_M sunt ordonate alfabetic si sunt scrise cu majuscule
Lungimea oricarui cuvânt este de maxim 100 de litere
1 <= N <= 100
T_i apartine multimii {1, 2, ..., 9}, pentru orice i din {1, 2, ..., N}

Timp maxim de executie/test: 0.1 secunde

prof. Serban Marinel
Liceul de Informatica "Gr. C. Moisil" Iasşi
Contact: marinel_serban_at_yahoo.com