Bizda quyidagi matn bor bo’lsin

Rabin-Karp algoritmi qanday ishlaydi?

Belgilar ketma-ketligi olinadi va kerakli qatorning mavjudligi uchun tekshiriladi. Agar imkoniyat topilsa, belgilarni moslashtirish amalga oshiriladi.
Keling, algoritmni quyidagi bosqichlar bilan tushunamiz:

1. 
   Matn shunday bo'lsin: Matn
   Va yuqoridagi matnda qidiriladigan satr: Naqsh
   
2. 
   Keling numerical value(v)/weight, muammoda foydalanadigan belgilar uchun a belgilaymiz. Bu erda biz faqat birinchi o'nta alifboni oldik (ya'ni A dan J gacha). Matn og'irliklari
   
3. 
   nnaqsh uzunligi bo'lsin vammatn uzunligi bo'lsin. Mana, m = 10 and n = 3.
   Letdkirish to'plamidagi belgilar soni bo'lsin. Bu erda biz {A, B, C, ..., J} kirish to'plamini oldik. Shunday qilib, d = 10. uchun har qanday mos qiymatni qabul qilishingiz mumkind.
   
4. 
   Keling, naqshning hash qiymatini hisoblaylik. Matnning xesh qiymati
   

naqsh(p) = S(v * dm-1) mod 13 uchun xesh qiymati
= ((3 * 10 ² ) + (4 * 10 ¹ ) + (4 * 10 ⁰ )) 13-modda
= 344 mod 13
= 6
Yuqoridagi hisobda tub sonni (bu yerda, 13) shunday tanlangki, biz barcha hisoblarni bitta aniqlikdagi arifmetika bilan bajara olamiz.
Modulni hisoblash sababi quyida keltirilgan .

5. 
   O'lchamdagi matn oynasi uchun xesh qiymatini hisoblangm.
   

Birinchi oyna ABC uchun,
text(t) = S(v * dn-1) mod 13 uchun xesh qiymati
= ((1 * 10 ² ) + (2 * 10 ¹ ) + (3 * 10 ⁰ )) 13-modda
= 123 mod 13
= 6

6. 
   Naqshning xesh qiymatini matnning xesh qiymati bilan solishtiring. Agar ular mos kelsa, belgilarni moslashtirish amalga oshiriladi.
   Yuqoridagi misollarda birinchi oynaning xesh qiymati (ya'nit) bilan mos keladipShunday qilib, ABC va CDD o'rtasidagi belgilar mosligiga o'ting. Ular mos kelmagani uchun keyingi oynaga o'ting.
   
7. 
   Biz keyingi oynaning xesh qiymatini birinchi atamani ayirib, quyida ko'rsatilgandek keyingi atamani qo'shish orqali hisoblaymiz.
   

t = ((1 * 10 ² ) + ((2 * 10 ¹ ) + (3 * 10 ⁰ )) * 10 + (3 * 10 ⁰ )) mod 13
= 233 mod 13
= 12
Ushbu jarayonni optimallashtirish uchun biz avvalgi xesh qiymatidan quyidagi tarzda foydalanamiz.
t = ((d * (t - v[olib tashlanadigan belgi] * h) + v[qo'shiladigan belgi] ) mod 13
= ((10 * (6 - 1 * 9) + 3) mod 13
= 12
Bu yerda, h = d ^m-1 = 10 ^3-1 = 100.

8. 
   BCC uchun t = 12 ( ≠ 6). Shuning uchun, keyingi oynaga o'ting.
   Bir necha qidiruvdan so'ng biz oyna uchun moslikni olamizCDAmatnda. Turli oynalarning xesh qiymati