Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.
Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin. Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Substring larni hisoblashning qanday eng tez algoritmini bilasiz?

+7 ovoz
87 marta ko‘rilgan
so‘radi 25 dekabr, 16 abdujabbor (399 bal)
tahrirlandi 03 mart, 17 vejon

Masala sharti quyidagicha:
n uzunlikdagi s string berilgan. q ta query dagi substringlarni unique substringlarini sonini topish kerak

Input: 1 <= n, q <= 10^5

Birinchi qatorda n va q sonlari beriladi keyin s string kiritiladi.
Keyingi q ta qatorda left, right indexlar beriladi. Va shu s[left:right + 1] string uchun substringlar sonini ekranga chiqarish kerak bo'ladi:
Misol:

5 5
aabaa
1 1
1 4
1 1
1 4
0 2

Javobi:

1
8
1
8
5


Shu masalani eng tez topish algoritmi bormi? 10 ^ 5 bo'lgani uchun TIMEOUT da qolib ketadi ko'p holatlarda. Xususan o'zim suffix array va lcp lar orqali hisoblab ko'rdim. Lekin bu variantimiz 10 ^ 5 uchun to'g'ri kelmaydi. Biron bir optimal yechimga taklif bormi???

Mana bu men yozgan yechim, 30% testlardan o'tdi xolos:

https://gist.github.com/Abdujabbor/0102ced17259b9db778b11032bf5dd21

izoh qoldirdi 26 dekabr, 16 oakrom (388 bal)
Shu misolingizni kodini ham yozing, algoritmni realizatsiyasini ham ko'raylik, yordam berish osonroq bo'lardi.
izoh qoldirdi 26 dekabr, 16 abdujabbor (399 bal)
source ni qoldirdim Akrom aka.

Iltimos, saytga kiring yoki ro‘yxatdan o‘ting va shunda ushbu savolga javob berishingiz mumkin bo‘ladi.

Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.

Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin.

Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Telegram kanal YordamUzRss

...