2-qadam.
Agar
m
qismiy satr uzunligi bo'lsa, biz matn satrining
boshidan m uzunlikdagi qismiy satrni olishni boshlaymiz. Shundan
so'ng, qismiy satr uchun xesh-kod qiymatini topamiz va shablon
satrining xesh-kod qiymatiga mos kelishini tekshiramiz. Agar u mos
keladigan bo'lsa, belgini birma-bir tekshiradi, aks holda keyingi qismiy
satrga o'tadi.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
1
5
22 5
Xesh kod qiymati: 1+5+22+5 = 33
Xesh-kod qiymati mos kelmaydi, keyin biz
m
(4) uzunlikdagi
keyingi satrga o'tamiz.
191
3-qadam.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
5
22 5
19
Xesh kod qiymati: 5+22+5+19 = 51
Xesh-kod qiymati mos kelmaydi, keyin
m
uzunlikdagi keyingi
satrga o'tamiz.
4-qadam.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
22 5
19 1
Xesh kod qiymati: 22+5+19+1 = 47
Xesh-kod qiymati mos kelmaydi, keyin biz
m
uzunlikdagi keyingi
satrga o'tamiz.
5-qadam.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
5
19 1
16
192
Xesh kod qiymati: 5+19+1+16 = 41
Bu yerda xesh-kodining qiymati bir xil, shuning uchun biz ichki
qismiy belgilarini qidiriluvchi satr bilan birma -bir tekshiramiz.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
e
s
a
p
Barcha belgilar mos keladi, keyin biz ichki satrning boshlangʻich
indeksini chop etamiz va iloji bo'lsa,
m
uzunlikdagi keyingi qismiy
satrga o'tamiz.
6-qadam.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
19 1
16 14
Xesh kod qiymati: 19+1+16+14 = 50
Joriy ichki satrning xesh qiymati qismiy satrning xesh qiymatiga
mos kelmaydi. Shunday qilib, iloji bo'lsa, m uzunligining keyingi ichki
satriga oʻtamiz, aks holda to'xtatamiz.
7-qadam.
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
↓
↓
↓
↓
1
16 14 7
193
Xesh kod qiymati: 1+16+14 +7= 38
Bu yerda ham xesh kodi qiymati mos kelmaydi va bu
m
uzunligining oxirgi ichki satri. Shunday qilib, bu yerda o'z jarayonimizni
to'xtatamiz.
Eslatma:
Bu yerda xesh funksiyasini yaratish yoki aniqlashning
turli usullari mavjud. Yaxshi tushunish uchun oddiy xesh funksiyasidan
foydalanildi.
Rabin-Karp algoritmi (C++)
#include
using namespace std;
void rabin_karp(string &text,string &pattern, int q)
{
/*qismiy satr uzunligi*/
int m = pattern.length();
/*Berilgan satr uzunligi*/
int n = text.length();
int p=0,t=0,h=1,d=26; // bu yerda p - matn uchun xesh qiymati, t – qismiy
satrning xesh qiymati;
/*h=pow(d,M-1) bu yerda d - 26, agar matnda faqat katta harflar bo'lsa.*/
for(int i=0;i
{
h=(h*d)%q;
}
/* matn va m uzunligining birinchi ichki satri uchun xesh qiymatini hisoblash
*/
for(int i=0;i
{
p=(d*p+pattern[i])%q;;
t=(d*t+text[i])%q;
}
/* m uzunlikdagi qolgan satr uchun */
for(int i=0;i<=n-m;i++)
{
194
/* agar xesh qiymatlari bir xil bo'lsa, xeshni ichki satr va qismiy satridagi
belgilar bo'yicha tekshirish */
if(p==t)
{
int flag=0;
for(int j=0;j
{
if(text[i+j]!=pattern[j])
{
flag=1;
break;
}
}
/* agar barcha belgilar mos keladigan bo'lsa, ichki satrning boshlangʻich
indeksini chop etish.*/
if(flag==0)
{
cout<<" Indeksda berilgan satr osti topildi:"<
|
