SamDUKF biznesni boshqarish va axborot texnologiyalari fakulteti AT.21-13 guruh talabasi Jurayeva Oydinisoning “algoritm va berilganlar strukturasi” fanidan tayyorlagan taqdimoti MAVZU:
Rabin-Karp algoritmi-bu matnni xeshlash yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U 1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan. Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi bir nechta qismiy satr uchun moslikni topishda juda samarali. n uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va eng yaxshi bajarilish vaqti to'gʻri xesh funksiyasi bilan O (n) dir, lekin eng yomon holatda uning samaradorligi O (nm) ga teng. Bu esa keng qo'llanilmasligining sabablaridan biridir.
Quyidagi misol orqali Rabin-Karp algoritmini koʻrib chiqamiz. Berilgan matn S= “aevesapng”‖ Izlanadigan satr P= “esap”
Do'stlaringiz bilan baham: |
