Bitiruv malakaviy ishi mavzu: Axborotlashtirish obyektlarni ximoyalashda qo'laniladigan tarmoqlararo ekran tahlili. Bajardi: 715-20 – guruh talabasi Bo'riyev O. Ilmiy rahbar: Raximov Rustam s a m a r q a n d – 2015

Misollar.  
n(aba)=a, n(n(aba))=n(a)=L;
n(abab)=ab, n(n(abab))=n(ab)=L;
n(ababa)=aba, n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=n(abc)=L;
Kelgusida ishlatiladigan bir nechta ma’lumotlarni isbotlaymiz, ya’ni 
quyidagi tasdiqlarni: 
(1) n(X),n(n(X)),n(n(n(X))),...,L so’zlar ketma-ketligi “uziladi” (L bo’sh 
so’zda). 
(2) Barcha n(X),n(n(X)),n(n(n(X))),...,L so’zlar X so’zining boshi 
hisoblanadi. 

---

31 
(3) Bir vaqtda X so’zining boshi va oxiri bo’lgan ixtiyoriy so’z (X ning 
o’zidan boshqa) n(X),n(n(X)),....,L ketma-ketlikka kiradi. 
Isboti. 
(1) Trivial, chunki har bir so’z oldingisidan qisqa. 
(2) Ulardan har biri (ta’rifga ko’ra) oldingisining boshi bo’ladi. Shunga 
ko’ra ularning barchasi X so’zining oxirlari bo’ladi. 
(3) Y so’zi bir vaqtda X ning oxiri va boshi bo’lsin, n(X) so’zi bunday 
so’zlardan eng uzuni. Shuning uchun, Y n(X) dan uzun emas. Bu ikkala so’z X 
ning boshida bo’ladi, ulardan qisqarog’i uzunrog’ining boshi bo’ladi: Y n(X) uning 
boshi. Shunga o’xshash Y n(X) oxiri. Induksiya bo’yicha fikr yuritib, faraz qilish 
lozimki, masala tasdig’i X dan qisqa barcha so’zlar uchun, xususan, n(X) so’zi 
uchun to’g’ri. Y so’z n(X) oxiri va boshi bo’lib, yo n(X)ga teng, yoki 
n(n(X)),n(n(n(X))),...,L ketma-ketlikka kiradi. 
KMP usuli izlanayotgan satrni oldindan qayta ishlashdan foydalanadi, ya’ni 
uning asosida prefiks funksiya yaratiladi. Bunda quyidagi g’oyadan foydalaniladi. 
Agar i uzulikdagi so’z prefiksi (u ham suffiks) bitta simvolga uzun bo’lsa, u holda
bir vaqtda i-1 uzunlikdan qism satr prefiksi ham bo’ladi.
Shunday qilib, biz oldingi qism satr prefiksini tekshiramiz. Agar u to’g’ri 
kelmasa, u holda uning prefiksining prefiksini tekshiramiz va hakozo. Shunday ish 
yuritib, eng katta izlanayotgan prefiksni topamiz. Navbatdagi savol: nima uchun 
prosedura ish vaqti chiziqli, unda ichki joylashgan sikl borku? Bizga undan 
prefiks-funksiyani berish m marta ro’y beradi, qolgan vaqtda k o’zgaruvchi 
o’zgaradi. while siklda u(P[k]uchun shunga qaraganda kam bo’lmagan marta kamayishi mumkin. K o’zgaruvchi 
birga m dan ko’p bo’lmagan marta o’sadi. Demak, k o’zgaruvchi jami ikki 
martadan ko’p bo’lmagan holda o’zgaradi. Bunday butun prosedura ish vaqti
O(m) ga teng [7,8]. 
Hozir satrda qism satrni izlovchi algoritmning o’ziga o’tamiz. 

---

32 
Bu dastur chiziqli vaqt ishlashini isbotlash uchun prefiks-funksiya kabi aniq 
bajarilishi mumkin. 
Yakunida ta’kidlaymizki, ketma–ket izlash algoritmi va KMP algoritmi 
satrlarning o’zlarini tanishdan tashqari, ish davomida nechta simvol mos tushishini 
sanaydi.