Masala #0852

Xotira 512 MB Vaqt 2000 ms
14

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".