Bizda quyidagi matn bor bo’lsin

Satrlarni moslashtirish algoritmi "String qidirish algoritmi" deb ham ataladi. Bu string algoritmining muhim klassi bo'lib, "bu kattaroq satr ichida bir nechta satrlar joylashgan joyni topish usuli" deb e'lon qilinadi.

n ta belgidan iborat T [1.....n] matn massivi va m ta belgidan iborat P [1......m] naqsh massivi berilgan. Muammolar 0 <= s < nm va T [s+1......s+m] = P [1......m] bo'lgan haqiqiy siljish deb ataladigan s butun sonini topishdir . Boshqacha qilib aytadigan bo'lsak, Tda P bo'lsa ham topish uchun, ya'ni bu erda P T ning pastki qatori bo'lsa. P va T elementi {0, 1} yoki {A, B kabi chekli alifbodan chizilgan belgilardir ... ..Z, a, b..... z}.T [1......n] qatori berilgan boʻlsa, quyi qatorlar  baʼzi 0 < uchun T [i......j] koʻrinishida ifodalanadi. = i <= j <= n-1, i indeksdan j indeksigacha boʻlgan T dagi belgilar tomonidan hosil qilingan qator. Ushbu jarayon satrning o'z-o'zidan pastki qator bo'lishi (i = 0 va j = m ni oling). 

T [1......n] qatorining to'g'ri pastki  qatori ba'zi 00 yoki j < m-1 bo'lishi kerak.

Turli xil string moslama algoritmlari mavjud, ammo ular orasida eng ko'p qo'llaniladi.

Naive String Matching algoritmi naqshni birma-bir siljitadi . Har bir slayddan keyin u joriy siljishdagi belgilarni birma-bir tekshiradi va agar barcha belgilar mos kelsa, moslikni chop etadi. 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:
1) Shaklning o'zi.
2) m uzunlikdagi matnning barcha pastki qatorlari.
Matnning m o'lchamdagi barcha pastki satrlari uchun xesh qiymatlarini samarali hisoblashimiz kerakligi sababli, biz quyidagi xususiyatga ega bo'lgan hash 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.
Rabin va Karp tomonidan tavsiya etilgan xesh funksiyasi butun sonni hisoblab chiqadi. Satr uchun butun son qiymati satrning raqamli qiymatidir. Misol uchun, agar barcha mumkin bo'lgan belgilar 1 dan 10 gacha bo'lsa, "122" ning raqamli qiymati 122 bo'ladi. Mumkin bo'lgan belgilar soni 10 dan yuqori (umuman 256) va naqsh uzunligi katta bo'lishi mumkin. Shunday qilib, raqamli qiymatlarni amalda butun son sifatida saqlash mumkin emas. Shuning uchun, son qiymat modulli arifmetika yordamida hisoblab chiqiladi, bu xesh qiymatlari butun o'zgaruvchida saqlanishi mumkinligiga ishonch hosil qilish uchun (xotira so'zlariga sig'ishi mumkin). Qayta ishlash uchun biz eng muhim raqamni olib tashlashimiz va xesh qiymatiga yangi eng kam ahamiyatli raqamni qo'shishimiz kerak. Qayta tiklash quyidagi formula yordamida amalga oshiriladi.
hash( txt[s+1 .. s+m] ) = ( d ( hash( txt[s .. s+m-1]) - txt[s]*h ) + txt[s + m] ) mod q
hash( txt[s .. s+m-1] ) : s shiftdagi xesh qiymati .
hash( txt[s+1 .. s+m] ) : Keyingi siljishdagi xesh qiymati (yoki siljish s +1)
d : Alifbodagi belgilar soni
q : tub son
h: d^(m-1)
Yuqoridagi formulaning ishlashi: 
Bu oddiy matematika, biz oldingi oynadan joriy oynaning kasr qiymatini hisoblaymiz.
Misol uchun, naqsh uzunligi 3 va satr %u201C23456%u201D
Siz birinchi oynaning qiymatini (bu %u201C234%u201D) 234
deb hisoblaysiz. Keyingi oynaning qiymatini %u201C345%u201D qanday hisoblaysiz? Siz (234 %u2013 2*100)*10 + 5 ni bajarasiz va 345 ni olasiz.