Concursul "Urmasii lui Moisil" 2002 Clasa a IX-a

Problema 2- T9

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 separate 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 data o tasta. La actionarea unei taste este afisat primul cuvânt din dictionar care contine, pe pozitia respectiva, una din 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 din literele ABC pe prima pozitie
9 AZI adica una din literele WXZY pe pozitia a doua
4 AZI adica una din 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.
Se vor verifica toate posibilitatile de formare a unui cuvânt conform regulilor de mai sus.
Aranjarea literelor pe tastatura telefonului mobil este urmatoarea:

Cerinta

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

   M                      - numarul de cuvinte din dictionar
   C1                     - C1, C2, …, CM reprezinta cuvintele din dictionar
   C2
   …
   CM
   N                      - numarul de taste actionate
   T1 T2 … TN             - cifrele înscrise pe cele N taste actionate

Date de iesire
Fisierul de iesire T9.OUT contine pe o singura linie mesajul generat de sistemul T9 în urma apasarii celor N taste.

Restrictii
- 1 <= M <=100;
- Cuvintele C1, C2, …, CM sunt ordonate alfabetic si sunt scrise cu majuscule;
- Lungimea oricarui cuvânt este de maxim 100 de litere.
- 1 <=N <=100
- Ti in {1, 2, …, 9}, pentru orice i din {1, 2, …, N}

Exemple

Timp maxim de executie: 1 secunda/test