Masala #0526

Xotira 10 MB Vaqt 500 ms Qiyinchiligi 35 %
3.2 (Baholar 8)
14

  

Qidiruv

Sizga ss va tt satrlar berilgan bo’lib, ss satr ichidan tt satrni qidirishingiz talab etiladi. tt satr ?? belgisi va lotin alifbosining kichik harflaridan tashkil topgan. ?? belgisi bu lotin alifbosinng kichik harflaridan istalgan biri deb qarash mumkun. Sizning vazifangiz ss satr ichidan mumkun bo’lgan holatlarda qancha tt satrni qirqib olish mumkin, agar qirqib olishning imkoni bo’lsa, har bir qirqib olish mumkin bo’lgan s[i,j](ij)s[i,…j] (i\leq j) satrning i-chi indeksini topish talab etiladi.


Kiruvchi ma'lumotlar:

Kirish fayilining dastlabki satrida q(1q100)q (1\leq q\leq 100) testlar soni. Keyingi 2q2q ta satirda mos ravishda ss va tt lar kiritiladi ss,tt(1s50000,1t100)(1\leq |s|\leq 50000, 1\leq |t|\leq 100). Kiruvchi ma’lumotlarda ss faqatgina lotin alifbosining kichik harflaridan, tt esa lotin alifbosining kichik harflari va ?? belgisidan tashkil topgan.  


Chiquvchi ma'lumotlar:

Jami qq ta testga javobni chiqaring. ss satr ichidan tt satrni jami nechi xil usulda qirqib olish mumkinligi va keyingi satrda qirqib olish nechinchi indeksdan boshlanishini chop eting, agar birorta ham mavjud bo’lmasa mos ravishda 0 va bo’sh joyni chop eting.


Misollar
# input.txt output.txt
1
5
abacaba
a?a
test
?????
abaabaaab
a??a
ok
?
contest
??t
3
0 2 4 
0

3
0 2 3 
2
0 1 
2
1 4 
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin