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
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
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 |