== include(page="template/taskheader" task_id="radio2") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $radio2.in$ ...
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).
h2. Date de ieşire
În fişierul de ieşire $radio2.out$ ...
Î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.
h2. 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$.
h2. Exemplu
table(example). |_. radio2.in |_. radio2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 3 6 2
anaaremere
roaane
aareme
renere
| 0
1
1
|
h3. 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.
== include(page="template/taskfooter" task_id="radio2") ==
