Bizda quyidagi matn bor bo’lsin

8.1-rasm: string xeshini hisoblash uchun xeshlash funksiyasi, bunda belgilar to'plamining o'lchami b va p nisbatan b ga nisbatan tubdir .

Modulo xususiyatlari

Yuqorida aytib o'tilganidek, 8.1- rasmda berilgan xesh funktsiyasini C tilida amalga oshirish qiyin (yoki imkonsiz). Muammo shundaki, C dagi butun sonlar ma'lum bitlar soniga ega (odatda 32 yoki 64, lekin 16 bitli mashinalar odatiy emas. ). b va n qiymatlariga qarab , atama int (yoki har qanday oddiy C turi) ga sig'maslik uchun juda katta bo'lishi muqarrar bo'lishi mumkin. Masalan, agar b = 256 bo'lsa, yig'ish natijasi 32 bitli butun songa mos kelishi uchun n 4 yoki undan kichik bo'lishi kerak.
Yaxshiyamki, biz modul operatsiyasining muhim xususiyatidan foydalanishimiz mumkin - qo'shish, ko'paytirish yoki ayirish hisobining oraliq bosqichlari modulini olish hisoblash natijasiga ta'sir qilmaydi. Masalan, har qanday va uchun:

Bu shuni anglatadiki, modul operatsiyasini erta va tez-tez bajarib, biz foydalanayotgan modul unchalik katta bo'lmasa, biz juda katta sonlar ustida amallar natijalarining modulini raqamlarning o'lchami haqida hech qachon tashvishlanmasdan hisoblashimiz mumkin.

Masalan, biz hisoblashni xohlaymiz, deb tasavvur qiling, bu erda va juda katta sonlar, lekin b kichik raqam. Mahsulot juda katta raqam bo'ladi- lekin biz u bilan hech qachon shug'ullanishimiz shart emas, chunki va ta'rifiga ko'ra, natija har doim 0 va b - 1 oralig'ida bo'lishi kerak .
Oraliq bosqichlarda modulni tajovuzkorlik bilan qabul qilish orqali biz juda katta raqamlardan foydalanishdan umuman qochishimiz mumkin.

Misol

Tasavvur qiling, biz hisoblashni xohlaymiz. Avval 10, 7 ning bir nechta kuchlarini hisoblash foydalidir:

Ushbu qiymatlarni hisobga olgan holda hisoblash oson:

Rabin-Karpni tezlashtiradigan hiyla

Rabin-Karp qatorlarini qidirish algoritmini samarali qiladigan hiyla shundaki, biz qo'shni pastki satrlar uchun hisoblash oson bo'lgan xesh funktsiyasini tanladik - birinchi pastki qatorning xesh qiymatini bilganimizdan so'ng, xesh qiymatini hisoblashimiz mumkin. O (1) vaqtidagi keyingi . Bunga modul operatsiyasining xususiyatlaridan yana bir bor foydalanish orqali erishiladi.
Misol uchun, biz matn va naqsh qatori faqat 0 dan 9 gacha bo'lgan belgilardan iborat alifbodan chizilgan deb tasavvur qiling. Matn ``234591'' va biz 4 uzunlikdagi naqshni qidirmoqdamiz. Biz allaqachon hisoblab chiqdik. Hisoblashda yordam berish uchun bundan qanday foydalanishimiz mumkin?
2345 ni 3459 ga quyidagi bosqichlar orqali aylantirish mumkinligiga e'tibor bering:

1. 
   2345 ni 10 ga ko'paytiring, 23450 ni hosil qiling.
   
2. 
   23450 dan 20000 ni ayirib, 3450 ni qoldiring. Bu o'ngga siljigan ''2'' raqamining effektini o'chiradi.
   
3. 
   9 qo'shing, 3459. Bu ``9'' raqamini qo'shadi.
   

Ushbu usuldan foydalanish quyidagi hisob-kitoblarga olib keladi:

Xuddi shunday, biz bilganimizdan so'ng, ushbu bilimdan yuqoridagi kabi hisoblash uchun foydalanish oson: