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.
Cerinţă
Voi trebuie să îi spuneţi Laurei, pentru fiecare dintre 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
radio1.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
radio1.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
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.
Exemple
radio1.in | radio1.out | Explicaţii |
10 3 6 2
anaaremere
roaane
aareme
renere
| 0
1
1
| 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 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.
|