Masala #0852

Xotira 512 MB Vaqt 2000 ms

Rabin- Karp

Rabin - Karp algoritmini urganish jarayonida qiziq bir narsa meni o'ylantirib qoldi. Sizga inglizcha harflardan iborat s satr beriladi. s satrni Pastki qator(substring)\(s[l...r](1 \leq l \leq r \leq \vert s \vert)\) larida yomon deb berilgan harflar soni ko'pi bilan k ta bo'lganlari sonini toping.
Agar 2 ta \(s[x...y] ≠ s[p...q]\) bo'lmasa ular har xil hisoblanadi, yani mano jihatidan bir xil bo'lmasligi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda s satr uzunligi 1500 dan oshmaydi.
Ikkinchi qatorda 26 ta harf uchun yaxshi yoki yomon ekanini belgilovchi '0' va '1' lardan iborat satr kiritiladi('0' bo'lsa yomon , '1' bo'lsa yaxshi).
Ohirgi qatorda k(\(0 \leq k \leq |s|\)) butun son kiritiladi.

Chiquvchi ma'lumotlar:

Berilgan shartni qanoatlantiruvchi satrlar sonini toping.

Misollar

#	input.txt	output.txt
1	acbacbacaa 00000000000000000000000000 2	8

Izoh:

1-Test uchun: Berilgan shartlarni qanoatlantiruvchi satrlar "a", "aa", "ac", "b", "ba", "c", "ca", "cb".