Masala #0558

Xotira 256 MB Vaqt 1000 ms Qiyinchiligi 30 %
14

  

Lochinbek va Z-funksiya

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.


Misollar
# input.txt output.txt
1
sasrsas
3
1 4
3 2
7 1
2
sss
3
1 3
2 2
3 1
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.

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