| Fişierul intrare/ieşire: | radio2.in, radio2.out | Sursă | Lot Alba Iulia 2010, Baraj 3 |
| Autor | Alexandru Tomescu, Paul-Dan Baltescu | Adăugată de |  Dragos-Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Radio2
Laura a dezvoltat recent o pasiune pentru şirurile de caractere generate aleator. Ca să o ajute să treacă mai uşor peste sesiune, prietenii ei s-au gândit să o înveselească şi i-au cumpărat un astfel de şir de lungime N, conţinând doar litere mici ale alfabetului englez. De dimineaţă, Laura a început să asculte muzică la radio şi a auzit M cuvinte, toate având aceeaşi lungime L, care i-au plăcut foarte mult. Aceste cuvinte sunt formate tot din litere mici ale alfabetului englez. Acum ea şi-ar dori să vadă, pentru fiecare cuvânt, dacă acesta apare ca subsecvenţă în şirul primit cadou. Cum cuvintele sunt destul de lungi, Laura nu este sigură că le-a auzit corect, dar este convinsă că nu a înţeles greşit mai mult de K litere din fiecare cuvânt.
Aşadar, voi trebuie să îi spuneţi, pentru fiecare din cele M cuvinte, dacă există o subsecvenţă de lungime L în şirul primit cadou astfel încât cuvântul şi subsecvenţa să difere în cel mult K poziţii.
Date de intrare
Pe prima linie a fişierului de intrare radio2.in se află 4 numere întregi N M L K, având semnificaţia din enunţ. Pe următoarea linie, se află N caractere neseparate prin spaţii ce reprezintă şirul primit cadou de fată. Pe următoarele M linii, se află câte L caractere neseparate prin spaţii, ce reprezintă cuvintele pe care Laura le-a auzit la radio (aşa cum le-a înţeles ea).
Date de ieşire
În fişierul de ieşire radio2.out va conţine M linii. Pe linia i (1 ≤ i ≤ M), veţi afişa 1 dacă există o subsecvenţă în şirul primit cadou de fată care să difere în cel mult de K poziţii de al i-lea cuvânt din fişierul de intrare, respectiv 0, în caz contrar.
Restricţii
- 1 ≤ N ≤ 1 000 000
- 1 ≤ M ≤ 500
- 1 ≤ K ≤ 50
- 500 ≤ L ≤ 2500
- Printr-un şir de litere {'a'-'z'} generat aleator se înţelege un şir în care pe fiecare poziţie, oricare dintre literele {'a'–'z'} are aceeaşi probabilitate de apariţie.
- Pentru 10% din teste, N ≤ 10 000.
- Pentru 30% din teste, N ≤ 100 000.
- Pentru alte 10% din teste, K = 0.
Exemplu
| radio2.in | radio2.out |
|---|---|
| 10 3 6 2 anaaremere roaane aareme renere | 0 1 1 |
Explicaţie
Pentru cuvântul roaane nu există nici o subsecvenţă în anaaremere astfel încât cuvântul şi subsecvenţa să difere în mai mult de 2 poziţii. Cuvântul aareme apare exact în şirul dat, iar pentru renere există subsecvenţa remere faţă de care diferă printr-o singură poziţie.
Atenţie! Toate testele vor respecta condiţia a patra: 500 ≤ L ≤ 2500. Exemplul de mai sus nu respectă această restricţie şi nici nu este generat aleator, deoarece are ca scop înţelegerea enunţului.
