УЛІПО
Fransız yazıçısı Jorj Perec (1936–1982) bir dəfə "La disparition" adlı kitabını 'e' hərfi olmadan yazmışdı. O, dilin potensial imkanlarını elmi şəkildə araşdırmaq məqsədini qarşısına qoymuş yazıçı və riyaziyyatçılar birliyi olan ÜLİPO (fr. OULIPO, Ouvroir de littérature potentielle) qrupunun üzvü idi. Kitabdan bir sitat:
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Perec növbəti yarışmada daha yüksək (və ya əksinə, daha aşağı) bal ala bilərdi. Müəyyən bir mövzuda mümkün qədər az rast gəlinən "söz" ilə mətn yazmaq lazımdır (hətta mənasız ola bilər). Münsiflər heyətinə bu sözün mətndə neçə dəfə keçdiyini sayan bir proqram təqdim etmək lazımdır, beləliklə iştirakçıların reytinqi müəyyən edilir. İştirakçılar adətən uzun mənasız mətnlər yazırlar; məsələn, 500,000 ardıcıl 'T' hərfindən ibarət mətn qeyri-adi deyil. Və onlar heç vaxt boşluq istifadə etmirlər.
Biz sözün, yəni verilmiş sıranın mətndə nə qədər tez-tez rast gəldiyini tez bir zamanda cavablandırmaq istəyirik. Daha dəqiq desək: {'A', 'B', 'C', …, 'Z'} əlifbası və onun üzərində iki sonlu sıra var - söz W və mətn T. W sözünün T mətnində neçə dəfə rast gəldiyini saymaq lazımdır. W sözünün ardıcıl simvolları T mətninin ardıcıl simvolları ilə dəqiq uyğun gəlməlidir. Sözlərin keçişləri üst-üstə düşə bilər.
Giriş verilənləri
Birinci sətir testlərin sayını ehtiva edir. Hər bir test aşağıdakı formata malikdir:
Birinci sətir W sözünü ehtiva edir, {'A', 'B', 'C', …, 'Z'} əlifbasında yazılmışdır, burada 1 ≤ |W| ≤ 10000 ( |W| W sıranın uzunluğunu ifadə edir).
İkinci sətir T mətnini təyin edir, {'A', 'B', 'C', …, 'Z'} əlifbasında yazılmışdır, burada |W| ≤ |T| ≤ 1000000.
Çıxış verilənləri
Hər bir test üçün ayrı sətirdə bir ədəd çıxarın - W sözünün T mətnində rast gəlinmə sayını.