Üdvözlet (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Google Code Jam > 2009 > Qualification Round

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

S	M	S részstringje M-nek?
kutya	kaubtcyda	IGEN
kutya	kxutya	IGEN
kutya	kkuutya	IGEN, négyszer is
kutya	kutya	IGEN
macska	kutya	NEM

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.in	C-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.in	C-1.out
udv a szakkoron 3 udv a szakkoron uddv aaa szakkoron blablabla	Case #1: 0001 Case #2: 0012 Case #3: 0000

Tesztadatok

udvozlet.zip

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.