Bizda quyidagi matn bor bo’lsin

Rabin-Karp string qidiruvini amalga oshirish

Endi biz ushbu algoritmni C harflaridan iborat satrlar uchun C tilida qanday amalga oshirishni ko'rib chiqamiz.
8.1- rasmda berilgan funktsiyaga asoslangan xeshlash funksiyasi 8.2 -rasmda ko'rsatilgan . Funktsiyada modul m aniqlanmaganligini ham unutmang; bu ish vaqtida aniqlanishi mumkin bo'lgan parametrdir.

8.2-rasm: Xeshlash funksiyasi.
Haqiqiy satrlarni moslashtirish algoritmi 8.3- rasmda keltirilgan .

8.3-rasm: Rabin-Karp satrini qidirish algoritmi
Qabul qilingan birinchi amal - hisoblash bo'lib, u keyinchalik belgilar chapga `` o'chirilgan''ligi sababli xesh qiymatidan qancha miqdorni ayirish kerakligini aniqlash uchun ishlatiladi.
M katta bo'lgan vaziyatni chiroyli tarzda hal qilish uchun eksponensiallarni hisoblash uchun bo'lish va bosib olish algoritmi qo'llaniladi. Bu birinchi topshiriqda siz o'rgangan algoritm bilan bir xil, faqat modul erta va ko'pincha natijaning juda katta bo'lishiga yo'l qo'ymaslik uchun olinadi. Olingan funktsiyaning kodi 8.4 -rasmda ko'rsatilgan .

8.4-rasm: ni hisoblaydigan exp funksiyasi .
Keyingi harakat matnning nol siljishida naqsh va M uzunlikdagi pastki qatorni mashaqqatli ravishda xeshlashdan iborat. Bu xeshlash funksiyasidan foydalangan holda matnning pastki qatorini faqat shu vaqt ichida xeshlashimiz mumkin; barcha keyingi xeshlar avval tavsiflangan usul bilan hisoblanadi.
Biroq, satr bo'ylab ishlashni boshlashdan oldin, nolning o'zi mos kelishini tekshirishimiz kerak. Agar shunday bo'lsa, biz tugatdik. Aks holda, biz satrning qolgan qismini aylanib chiqamiz, har bir xeshni oldingisiga qarab hisoblaymiz ( 8.5- rasmda ko'rsatilgan nextHash funktsiyasidan foydalangan holda ).

8.5 - rasm: NextHash funksiyasi.

Rabin-Karpni tezlashtirish

Modulo operatsiyasidan qochish

Oldingi bo'limda ko'rsatilgan Rabin-Karp algoritmini amalga oshirish asl algoritmga sodiqdir, lekin ko'pgina zamonaviy kompyuterlarda uni bir oz suboptimal qiladigan kamchilik bor - u odatda nisbatan sekin bo'lgan modul operatsiyasiga tayanadi.
Shu bilan birga, modul operatsiyasini algoritmdan oldingi satrdan hisoblash oson bo'lgan, lekin juda ko'p modul operatsiyalarini talab qilmaydigan bir xil xususiyatga ega bo'lgan boshqa xeshlash funktsiyasini tanlash orqali chiqarib tashlash mumkin. Bunday funktsiyani yaratish usullaridan biri bir xil asosiy funktsiyani saqlab qolishdir, lekin har doim 2 quvvatga ega modulni tanlang, shuning uchun qimmatroq% operatsiya o'rniga bit niqoblaridan foydalanish mumkin . Albatta, 2 quvvatli moduldan foydalanish xeshlash funksiyasi uchun halokatli oqibatlarga olib keladi, agar funktsiya tomonidan ishlatiladigan b bazasi ham 2 ning kuchi bo'lsa- ko'pincha u shunday bo'ladi. Biroq, bu erda ham bizda biroz erkinlik bor - biz qilishimiz kerak bo'lgan narsa m ga nisbatan nisbatan asosiy bo'lgan b ni tanlashdir.- alifbodagi belgilar sonidan kattaroq har qanday raqam bajariladi.  Bunday holda, 257 ning b dan foydalanish xavfsiz tikish hisoblanadi.
Ushbu o'zgarishni amalga oshiradigan funktsiya 8.6 -rasmda ko'rsatilgan . Shuni esda tutingki, bu funktsiya o'zining b va m parametrlarini butunlay e'tiborsiz qoldiradi va buning o'rniga har doim b = 257 va m = 1024 dan foydalanadi. (Ushbu parametrlar saqlanib qoladi, shuning uchun bu funksiya stringSearchRK ning o'rnini bosuvchi sifatida ishlatilishi mumkin .)

8.6-rasm: Rabin-Karp algoritmini tezroq amalga oshirish, bu mod operatsiyasidan foydalanishdan qochadi.

Tasodifiylik orqali noto'g'ri o'yinlardan qochish

Bu erda keltirilgan Rabin-Karp algoritmi, agar matnda juda ko'p "noto'g'ri moslik" mavjud bo'lsa, juda sekin bo'lishi mumkin: naqsh bilan bir xil raqamga xeshlangan va shuning uchun qimmat memcmp bajarilishiga olib keladigan pastki qatorlar . b va m ni biladigan aqlli (yoki omadli) raqib bu algoritmni dahshatli bajaradigan matnlarni yaratishi mumkin.
Yechimlardan biri ish vaqtida m va b ni tasodifiy tanlash va har doim noto'g'ri mosliklar soni ko'p bo'lsa, tasodifiy yangi m va/yoki b ni tanlang .