Masala #0526

Xotira 10 MB Vaqt 500 ms Qiyinchiligi 35 %
14

  

Qidiruv

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


Kiruvchi ma'lumotlar:

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


Chiquvchi ma'lumotlar:

Jami \(q\) ta testga javobni chiqaring. \(s\) satr ichidan \(t\) 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