Bizda quyidagi matn bor bo’lsin

Rabin-Karp naqsh izlash algoritmi

• 
  Qiyinchilik darajasi: o'rta
  
• 
  Oxirgi yangilangan: 2022-yil 23-sentabr
  

 O'qing
 Muhokama qilish (40+)
 Kurslar
 Amaliyot
 Video
txt[0 matni berilgan . . .n-1] va naqsh pat[0. . .m-1] , txt[] da pat[] ning barcha takrorlanishini chop etadigan funksiya qidiruvini (char pat[], char txt[]) yozing. Siz n > m deb taxmin qilishingiz mumkin .
Misollar: 
Kirish: txt[] = “BU TEST MATNI”, pat[] = “TEST”
Chiqish: 10-indeksda namuna topilgan
Kirish: txt[] = "AABAACAADAABAABA", pat[] = "AABA"
Chiqish: 0-indeksda
topilgan naqsh 9-indeksda
topilgan naqsh 12-indeksda topilgan naqsh

Rabin-Karp algoritmi
Yondashuv: Muammoni hal qilish uchun quyidagi fikrga amal qiling:
Naive String Matching algoritmi naqshni birma-bir siljitadi . Har bir slayddan keyin joriy siljishdagi belgilar birma-bir tekshiriladi va agar barcha belgilar mos kelsa, moslikni chop eting.
Naive algoritmi singari, Rabin-Karp algoritmi ham naqshni birma-bir siljitadi. Ammo "Naive" algoritmidan farqli o'laroq, Rabin Karp algoritmi naqshning xesh qiymatini matnning joriy pastki qatorining xesh qiymatiga moslashtiradi va agar xesh qiymatlari mos kelsa, u faqat individual belgilarga mos kela boshlaydi. Shunday qilib, Rabin Karp algoritmi quyidagi satrlar uchun xesh qiymatlarini hisoblashi kerak.

• 
  Shaklning o'zi
  
• 
  m uzunlikdagi matnning barcha pastki qatorlari
  

Matnning m o'lchamli barcha pastki qatorlari uchun xesh qiymatlarini samarali hisoblashimiz kerakligi sababli, biz quyidagi xususiyatga ega bo'lgan xesh funktsiyasiga ega bo'lishimiz kerak :

• 
  Keyingi siljishdagi xesh joriy xesh qiymatidan va matndagi keyingi belgidan samarali hisoblanishi kerak yoki biz aytishimiz mumkinki, hash(txt[s+1 .. s+m]) hash(txt[s .. s ) dan samarali hisoblanishi kerak. +m-1]) va txt[s+m] , ya'ni hash(txt[s+1 .. s+m]) = rehash(txt[s+m], hash(txt[s .. s+m-) 1])) va
  
• 
  Rehash O(1) operatsiyasi bo'lishi kerak.