A. Prefiks satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Prefiks satr deb berilgan s satrning barcha s[0,i] (0 <= i <= |s|-1) qism satrlariga aytiladi.
Sizga berilgan s satrnig jami nechta bir biridan farqli prefiks satri bor ekanligini toping.

Kiruvchi ma'lumotlar:

Bitta qatorda lotin alifbosining kichik harflaridan tashkil topgan, uzunligi 1000 dan oshmaydigan va bo'sh bo'lmagan s satr.

Chiquvchi ma'lumotlar:

Bitta qatorda s satrning jami bir biridan farqli bo'lgan prefiks satrlari sonini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	a	1

B. Triple Z

Xotira: 64 MB, Vaqt: 2000 ms

Masala

Qism satr deb berilgan $s$ satrning istalgan $s[i,j] (0 \le i \le j \le |s|-1)$ satriga aytiladi. Misol uchun s="robocontest" satri uchun "robo", "ocon", "test", "b", "robocontest" kabi satrlar qism satr bo'la oladi.
Sizga berilgan 3 ta satr ichidan shunday qism satrlarni topingki, ular 3 ta satrda ham ishtirok etgan bo'lsin.

Kiruvchi ma'lumotlar:

3 ta qatorning har birida lotin alifbosining kichik harflaridan tashkil topgan, uzunligi 300 ta belgidan oshmaydigan va bo'sh bo'lmagan satrlar beriladi.

Chiquvchi ma'lumotlar:

Birinchi qatorda 3 ta satrda ham ishtirok etgan takrorlanmagan satrlarni sonini va keyingi qatorlarda esa ularning har birlarini alohida qatorda o'sish tartibi bilan chiqaring.

Izoh:

Satrlarda o'sish tartibi qoidasi sonlardan bir oz farq qilishini hisobga oling.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	samarqand qandolat andisha	6 a an and d n nd

C. Z - massivni hosil qilish #2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga $s$ satr berilgan bo’lib, bu satr orqali $Z$ massivni hosil qilish so’raladi.

$Z$ massivni hosil qilish quyidagicha amalga oshiriladi.

$Z$ massiv elementlari soni satr elementlari soniga teng bo'ladi va $Z$ massivning dastlabki qiymati uchun $0$ olinadi ya'ni $Z[0] = 0$ .
$Z[i] (i=1,2,...,len(s)-1)$ ni hosil qilish uchun $s$ satrning $i-index$ dan $s[i...j] (i\leq j)$ boshlanuvchi eng uzun quyi satr topiladi, $s$ satrning prefiks ga teng bo'lsin.
Topilgan bu sub satr uzunligi $Z[i]$ ga yoziladi (bunday satr mavjud bo'lmasa $0$ qiymati olinadi).

Prefiks bu satrning $0-index$ dan $s[0...j] (0\leq j)$ boshlanuvchi sub satrga aytiladi. Misol: $s = "abac"$ satrning prefikslari $a$ , $ab$ , $aba$ va $abac$

Kiruvchi ma'lumotlar:

Kirish faylida lotin alfbosining kichik harflaridan tashkil topgan $s(1\leq |s|\leq 10^6)$ satr beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida $Z$ massiv elementlarini probel bilan ajratilgan holda bitta satrda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	aabcaabc	0 1 0 0 4 1 0 0
2	aaaaaaa	0 6 5 4 3 2 1

D. Z - massivni hosil qilish #1

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga $s$ satr berilgan bo’lib bu satr orqali $Z$ massivni hosil qilish so’raladi.

$Z$ massivni hosil qilish quyidagicha amalga oshiriladi.

$Z$ massiv elementlari soni satr elementlari soniga teng bo'ladi va $Z$ massivning dastlabki qiymati uchun $0$ olinadi ya'ni $Z[0] = 0$ .
$Z[i] (i=1,2,...,len(s)-1)$ ni hosil qilish uchun $s$ satirning $i-index$ dan $s[i...j] (i\leq j)$ boshlanuvchi eng uzun quyi satr topiladi, $s$ satrning prefiks ga teng bo'lsin.
Topilgan bu quyi satr uzunligi $Z[i]$ ga yoziladi (bunday satr mavjud bo'lmasa $0$ qiymati olinadi).

Prefiks bu satrning $0-index$ dan $s[0...j] (0\leq j)$ boshlanuvchi quyi satrga aytiladi. Misol: $s = "abac"$ satrning prefikslari $a$ , $ab$ , $aba$ va $abac$

Kiruvchi ma'lumotlar:

Kirish faylida lotin alfbosining kichik harflaridan tashkil topgan $s(1\leq |s|\leq 10^3)$ satr beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida $Z$ massiv elementlarini probel bilan ajratilgan holda bitta satrda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	aabcaabc	0 1 0 0 4 1 0 0
2	aaaaaaa	0 6 5 4 3 2 1

E. Sub satrlar yig'indisi #1

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga $s$ satr berilgan bo'lib, sizning vazifangiz satrni barcha turli xil(bir biridan farqli) quyi satrlari uzunliklari yig'indisini aniqlashingiz kerak bo'ladi.

Misol: $s = "BOBR"$ satr uchun barcha turli xil sub satrlar $B$ , $O$ , $R$ , $BO$ , $OB$ , $BR$ , $BOB$ , $OBR$ , $BOBR$ . Bu sub satrlar uzunliklari yig'indisi $19$ ga teng.

Kiruvchi ma'lumotlar:

Kirish fayilida lotin alfbosining katta harflaridan tashkil topgan $s(1\leq |s|\leq 100)$ satr berilgan.

Chiquvchi ma'lumotlar:

Chiqish fayilida barcha turli xil sub satrlar uzunliklari yig'indisini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	BOBR	19
2	ROBOCONTEST	283

F. Sub satrlar yig'indisi #2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga $s$ satr berilgan bo'lib, sizning vazifangiz satrni barcha turli xil(bir biridan farqli) sub satrlari uzunliklari yig'indisini aniqlashingiz kerak bo'ladi.

Misol: $s = "BOBR"$ satr uchun barcha turli xil sub satrlar $B$ , $O$ , $R$ , $BO$ , $OB$ , $BR$ , $BOB$ , $OBR$ , $BOBR$ . Bu sub satrlar uzunliklari yig'indisi $19$ ga teng.

Kiruvchi ma'lumotlar:

Kirish faylida lotin alfbosining katta harflaridan tashkil topgan $s(1\leq |s|\leq 5000)$ satr berilgan.

Chiquvchi ma'lumotlar:

Chiqish faylida barcha turli xil sub satrlar uzunliklari yig'indisini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	BOBR	19
2	ROBOCONTEST	283

G. Nevara satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Prefiks satr deb berilgan $s$ satrning barcha $s[0,i] (0 \le i \le |s|-1)$ qism satrlariga aytiladi.
Suffiks satr deb berilgan $s$ satrning barcha $s[j,|s|-1] (0 \le j \le |s|-1)$ qism satrlariga aytiladi.
Nevara satr deb esa satrning prefiks va suffikslari yig'indisidan tashkil topgan satrga aytiladi.
Bu holatda bir marta ishlatilgan prefiks yoki suffiks boshqa ishlatilmaydi.

Sizning vazifangiz berilgan ikki satr uchun 2-satr 1-satrning Nevara satri bo'la oladimi yo'qmi topishingiz kerak.

Kiruvchi ma'lumotlar:

Ikkita qatorning har birida lotin alifbosining kichik harflaridan tashkil topgan, uzunligi 1000 dan oshmaydigan satrlar.

Chiquvchi ma'lumotlar:

Agar 2-qatordagi satr 1-qatordagi satrning Nevara satri bo'la olsa "yes" aks holda "no" chiqaring.

Izoh:

1-testda
dastur + lar

2-testda
robo+r+est

5-testda
format so'zini informatika so'zining suffiks va prefikslaridan yasab bo'lmaydi.

Misollar:


yes
yes
yes
yes
no

#	INPUT.TXT	OUTPUT.TXT
1	dasturchilar dasturlar	yes
2	robocontest roborest	yes
3	toshkent tosh	yes
4	alisher sherali	yes
5	informatika format	no

H. Lochinbek va Z-funksiya

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Lochinbek so'ngi kunlarda Z-funksiya mavzusida ko'p bilimlarga ega bo'ldi. U bilib olgan narsalari quyidagilar edi.

1. $S$ satr deb $S_1S_2S_3....S_{|s|}$ ko'rinishdagi satrga aytiladi. Bu yerda $S_i$ bu $S$ satrning elementlari $|S|$ esa $S$ satrning uzunligi.
2. $S[i..j] (1 ≤ i ≤ j ≤ |S|)$ qism satr deb $S_iS_{i + 1}...S_j$ ko'rinishdagi satrga aytiladi.
3. $S$ satrning $L (1 ≤ L ≤ |S|)$ uzunlikdagi prefiksi deb $S[1..L]$ satrga aytiladi.
4. $S$ satrning $L (1 ≤ L ≤ |S|)$ uzunlikdagi suffiksi deb $S[|S|-L+1..|S|]$ satrga aytiladi.

Sizning vazifangiz $S$ satrda ham prefiks, ham suffiks bo'la oladigan qism satrlar nechtaligini qaniqlash.

Kiruvchi ma'lumotlar:

Bitta qatorda kichik lotin harflaridan tashkil topgan $S_1S_2...S_{|s|} (1 ≤ |S| ≤ 10^5)$ satr.

Chiquvchi ma'lumotlar:

Birinchi qatorda $K$ soni. $K$ -ham prefiks ham suffiks bo'la oladigan satrlar soni.
Keyingi $K$ ta qatorda esa $L_i C_i$ sonlari. $Li$ ham prefiks ham suffiks bo'luvchi satr uzunligi $C_i$ esa shu prefiks(suffiks) $S$ satrda jami necha marotaba qism satr bo'lib kelganligi. $L_i C_i$ juftliklari $L_i$ o'sish tartibiga ko'ra chiqarilsin.

Izoh:

1-testda:
"sasrsas" so'zida "s" prefiksi bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 4 ta, "sas" bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 2 ta, "sasrsas" so'zining o'zi ham bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 1 ta.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	sasrsas	3 1 4 3 2 7 1
2	sss	3 1 3 2 2 3 1