Informatika gyűjtemény

Egy szinttel feljebb Üdvözlet

2004050607080910

NézetNyomtat

Üdv a szakkörön

Forrás: Google Code Jam 2009

feladat

Részstring

Egy S stringet M string részstringjének nevezzük, ha M-ből elhagyható úgy néhány (vagy nulla) karakter, hogy eredményül S-et kapjuk. Például:
SMS részstringje M-nek?
kutyakaubtcydaIGEN
kutyakxutyaIGEN
kutyakkuutyaIGEN, négyszer is
kutyakutyaIGEN
macskakutyaNEM

A kérdés

Arra leszünk kíváncsiak, hogy egy részstring hány különböző módon olvasható ki egy stringből. Bármely két kiolvasás különbözőnek számít, ha legalább egy karakter pozíciója eltér. Például a kkuutya esetében a részstring négy előfordulása:
kkuutya
=======
k u tya
 ku tya
k  utya
 k utya

Bemenet

A bemeneti fájl első sora S, a keresendő részstring. A következő sorban az N szám következik, majd N darab sor következik, és mindegyik egy M stringet tartalmaz, amiben majd S-et kell keresni részstringként.

Kimenet

A kimeneti fájl N darab sort tartalmazzon, mindegyik M stringhez egyet-egyet. A sorok formátuma a következő legyen: Case #i: j, ahol i az adott M string sorszáma 1-től kezdve; j pedig S előfordulásainak száma M-ben.
Mivel j értéke nagyon nagy is lehet, ezért kényelmi okokból csak az utolsó négy számjegyét kell kiírni. Ha j kisebb mint 9999, akkor az elejére annyi nullát kell írni, hogy a kiírt szám mégis négyjegyű legyen.

Példák

C-0.inC-0.out
welcome to code jam 3 elcomew elcome to code jam wweellccoommee to code qps jam welcome to codejam Case #1: 0001 Case #2: 0256 Case #3: 0000
C-1.inC-1.out
udv a szakkoron 3 udv a szakkoron uddv aaa szakkoron blablabla Case #1: 0001 Case #2: 0012 Case #3: 0000

Tesztadatok

Megjegyzés

A megoldott programokat a google code jam oldalán is ki lehet próbálni. Viszont van egy eltérés: az ott kapott tesztadatok elején nem szerepel a keresendő részstring, mert az mindig welcome to code jam.