DRŽAVNO NATJECANJE 2014. - Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Mirko se opet bavi UNIX-om.

Nedavno je otkrio da prilikom brisanja datoteka u komandnoj liniji ne mora nužno upisati točno ime datoteke koju briše nego može koristiti jednostavne regularne izraze.

Za ovu priliku se imena datoteka sastoje od samo malih slova engleske abecede.

Regularan izraz je niz znakova sastavljen od malih slova engleske abecede i znakova ‘*’ (zvjezdica).

Tako su na primjer ‘*’, ‘ab’, ‘a*’ i ‘b**c’ regularni izrazi.

Kažemo da ime datoteke X odgovara regularnom izrazu R ako se X može dobiti od R tako da se svaka zvjezdica u R zamjeni proizvoljnim nizom malih slova koji može biti i prazan (drugim riječima zvjezdica se može i obrisati).

Zvjezdice na različitim pozicijama mogu se zamijeniti različitim nizovima slova.

Ako kod brisanja datoteke umjesto imena datoteke koju želimo izbrisati napišemo regularni izraz, tada će se od svih datoteka u direktoriju obrisati točno one čije ime odgovara tom regularnom izrazu.

Na primjer, brisanje izraza ‘bbc’ obrisat će datoteke ‘bbc’, ‘bbcd’, ‘bbabaccccd’, ali neće obrisati datoteke ‘bbd’, ‘abbc’, ‘bacd’, ‘abc’.

Na njegovom računalu nalazi se više direktorija, a svaki sadrži jednu datoteku koju Mirko želi obrisati te još nekoliko datoteka koje ne smije obrisati.

Napišete program koji će, za svaki zadani direktorij, odrediti neki najkraći regularan izraz kojim Mirko može obrisati zadanu datoteku bez da obriše ostale datoteke u tom direktoriju.

Ulazni podaci

U prvom redu nalazi se prirodan broj D (1 ≤ D ≤ 5) koji označava broj različitih direktorija nakon čega slijedi prazan red.

Nakon toga slijedi D blokova međusobno odvojenih praznim redom, od kojih svaki blok predstavlja jedan direktorij.

U prvom redu bloka nalazi se ime datoteke koju je potrebno obrisati.

U drugom redu bloka nalazi se prirodan broj N (1 ≤ N ≤ 50), koji označava broj datoteka koje ne smiju biti obrisane.

Sljedećih N redova bloka sadrži imena datoteka koje ne smiju biti obrisane, svako ime u jednom redu.

Imena svih datoteka u jednom direktoriju (uključujući i datoteku koju je potrebno obrisati) će biti različita i sastojati će se od najviše 20 malih slova engleske abecede.

Izlazni podaci

Izlaz se sastoji od D redova, gdje svaki red sadrži najkraći izraz kojim se briše zadana datoteka bez da ostale datoteke u direktoriju budu obrisane.

Napomena: Rješenje će uvijek postojati, ali ne mora biti jedinstveno.

Primjer zadatka

ULaz

2
aac
2
bd
aae
zatvor
3
zatvora
bzatvor
czatvorddd

Izlaz

*c
z*r

Ulaz

1
bbabaccccd
4
bbd
abbc
bacd
abc

Izlaz

bba*