Masala #0932RSKXU4

Yaqinda tug'ilgan kuningiz munosabati bilan sizning g'ayrioddiy do'stingiz sizga "happy birthday" deb xabar yubordi:

hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu
hhapppyyyy biirtttthdaaay too youuu
happy birrrthdayy to youuu
happpyyyy birrtthdaaay tooooo youu

Avvaliga bu qo'shiqqa o'xshaydi, ammo chuqurroq o'rganib chiqqach, do'stingiz o'z xabari ichida "tug'ilgan kuningiz bilan" iborasini minglab marta yashirganini tushunasiz. Aslida, u 2 million martadan ko'proq narsani o'z ichiga oladi! Unga minnatdorchilik bildirish uchun aynan necha marta sodir bo'lganligi haqida javob berishni xohlaysiz.

Barcha hodisalarni hisoblash uchun protsedura quyidagicha: paragrafni ko'rib chiqing va "h" ni toping; keyin xatboshida "a" ni toping; undan keyin "p" ni toping va hokazo. Endi to'liq iborani yaratish uchun shu tarzda harflarni tanlash usullari sonini hisoblang.

Aniqrog'i, matn qatori berilgan bo'lsa, siz qidiruv qatori ushbu qatorning pastki ketma-ketligi sifatida necha marta paydo bo'lishini aniqlashingiz kerak.

Ikki argumentni talab qiladigan countSubsequences funksiyasini yozing: igna, qidiriladigan satr va haystack, izlash uchun satr. Bizning misolimizda "happy birthday" - igna, tug'ilgan kun xabari esa pichan. Funktsiya pichanning pastki ketma-ketligi sifatida igna necha marta sodir bo'lishini qaytarishi kerak. Bo'shliqlar ham ignaning bir qismi hisoblanadi.

Javoblar juda katta bo'lishi mumkinligi sababli, agar u 8 raqamdan oshib ketgan bo'lsa, javobning faqat oxirgi 8 raqamini qaytaring. Test holatlarining javoblari 8 ta raqamdan qisqa bo'ladi.

Birinchi qatorga needle kiritiladi

Ikkinchi qatorda haystack kiritiladi

Masalada so'ralgan javobni chop eting