189
Rabin-Karp algoritmining eng oddiy amaliy qo'llanmalaridan biri
plagiatni aniqlashdir. Rabin-Karp algoritmi
tekshirilgan maqoladagi
manba materiallardan ba'zi jumlalar paydo bo'lishining misollarini tezda
topishi mumkin. Algoritmning kichik farqlarga sezgirligini yo'q
qilish
uchun siz ularni olib tashlash orqali
harf yoki tinish belgi kabi
tafsilotlarni e'tiborsiz qoldirishingiz mumkin.
Biz qidirayotgan qatorlar
soni juda katta bo'lgani uchun, bitta satrlarni topishning an'anaviy
algoritmlari samarasiz bo'lib qoladi.
Quyidagi misol orqali Rabin-Karp algoritmini koʻrib chiqamiz.
Berilgan matn S= ―aevesapng‖
Izlanadigan satr P= ―esap‖
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
0
1
2
3
e
s
a
p
Quyida simvollar uchun xesh-kod keltirilgan:
a
→
1
b
→
2
c
→
3
d
→
4
e
→
5
f
→
6
… →
…
z
→
26
190
1-qadam
.
Belgilarga tayinlangan
xesh kodi yordamida qismiy
satrning xesh kodi qiymatini topamiz.
0
1
2
3
e
s
a
p
↓
↓
↓
↓
5
19 1
16
Xesh-kod qiymati: 5+19+1+16=41
