NézetNyomtat

Idegen nyelv (Megoldás)
Címkék > Feladat

Idegen nyelv

Forrás: Google Code Jam 2009
Több éves kutatás után brit tudósok felismerték egy idegen civilizáció rádióadását, amit egy távoli bolygóról sugároznak. Az idegen nyelv minden szava pontosan L kisbetűből áll, és pontosan D szó van a nyelvben.
Miután az idegen nyelv összes szavát beazonosították, rájöttek, hogy az idegenek évek óta küldenek üzeneteket a Földre. Sajnos ezek az üzenetek pontatlanul foghatók, a nagy távolság miatt. Az üzenetek megfejtéséhez el kell dönteni, hogy bizonyos minták hányféle módon értelmezhetők, vagyis az idegen nyelv hány különböző szava illeszthető a mintára.
Egy minta pontosan L tokenből áll. Egy token vagy egyetlen betű -- ilyenkor biztosan felismerték ezt a jelet az üzenetben - vagy különböző betűk sorozata zárójelek között. Például: (ab)d(dc) azt jelenti, hogy az első betű "a" vagy "b", a második biztosan "d", az utolsó pedig "d" vagy "c". Tehát az (ab)d(dc) mintára a következő 4 szó illeszkedik: add, adc, bdd, bdc.

Feladat

Írj programot, ami egy mintára eldönti, hány szó illeszkedik rá az idegen nyelvben!

Bemenet

A bemenet első sora L, D és N értékét tartalmazza, ahol N a tesztesetek száma. Utána D sorban az idegen nyelv szavai, majd N sorban a minták következnek.

Kimenet

A kimenet i. sora az i. mintára illeszkedő szavak számát írja le, a példában látható formában.

Méretek

Kis adatok

1 $\le$ L $\le$ 10
1 $\le$ D $\le$ 25
1 $\le$ N $\le$ 10

Nagy adatok

1 $\le$ L $\le$ 15
1 $\le$ D $\le$ 5000
1 $\le$ N $\le$ 500

Példa

Bemenet Kimenet
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

Tesztadatok