Üdv a szakkörön
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
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.
