Mavzu:Matnlar bilan ishlash Z-funksiyasi
Mundarija:
Kirish
I-bob.Z algaritmini qo’llash va ishlashi
1.1. Z algoritmi (chiziqli vaqt namunasini qidirish algoritmi)
1.2. Z algoritmi qo’llash
1.3. Z algoritmining ishlashi
II-bob.Z algaritmi amalga oshirish, satrini qidirish, misollar
2.1. Z algoritmining vaqt murakkabligi
2.2. Z algoritmini amalga oshirish
C/C++ da Z algoritmi
2.3. Z algoritmiga misollar
2.4. Z-algoritm satrini qidirish
Xulosa
Foydalanilgan adabiyotlar
Kirish
Mavzuning dolzarbligi:Z algoritmi qatorda berilgan naqshni izlash algoritmidir. Bu samarali algoritm, chunki u chiziqli vaqt murakkabligiga ega. U O(m+n) vaqt murakkabligiga ega , bu yerda m - satr uzunligi va n - izlanadigan naqsh uzunligi.Z algoritmi qatorda berilgan naqshni izlash algoritmidir. Bu samarali algoritm, chunki u chiziqli vaqt murakkabligiga ega. U O(m+n) vaqt murakkabligiga ega , bu yerda m - satr uzunligi va n - izlanadigan naqsh uzunligi.Berilgan satrdagi naqshga qanday mos kelishini o'ylab ko'rganmisiz, bu juda samarali. Misol uchun , agar siz DNK ketma-ketligini DNK naqshiga moslashtirishingiz kerak bo'lsa. DNK ketma-ketligi o'rtacha 150 milliardga yaqin uzunlikka ega. Bunday holatda qo'pol kuch satrini moslashtirish algoritmidan foydalanish juda yuqori ishlov berish vaqtlariga olib keladi, chunki u kvadratik vaqt murakkabligiga ega va undan foydalanishni amaliy bo'lmaydi.Xo'sh, bu muammoni hal qilish Z algoritmi bo'lishi mumkin , chunki u samarali qatorlarnimoslashtirish algoritmidir. Ko'proq bilish uchun o'qing.
Z algoritmi naqsh qidirish algoritmidir . Bu ma'lum bir naqshning satrdagi hodisalarini qidirish uchun ishlatilishini anglatadi. Bu samarali algoritm, chunki u chiziqli vaqt murakkabligiga ega.
Kurs ishining maqsadi: Matnlar bilan ishlash Z-funksiyasi mavzusini o’rganish
Kurs ishining tuzilishi: Kurs ish kirish, 2 bob, 6 bo‘lim, umumiy xulosalar va tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 42 sahifani tashkil qiladi
Do'stlaringiz bilan baham: |