195
cin>>pattern;
rabin_karp(text,pattern,97);
return 0;
}
Boyer-Mur algoritmi.
1977-yilda
Robert Boyer va Jey Mur
tomonidan
ishlab chiqilgan, matnda oldindan
ishlov berish imkoniyati
bo'lmagan
taqdirda, satrda qismiy satrni topish
algoritmlari orasida eng
tezkori hisoblanadi
.
Algoritm gʻoyasi quyidagicha:
-
Chapdan o'ngga skanerlash, o'ngdan chapga taqqoslash.
-
To'xtash
belgisini topish
o
agar taqqoslanadigan birinchi harf mos kelmasa, shablon eng
yaqiniga o'tkaziladi
o
to'xtash belgisi bo'lmasa, shablon
uning orqasiga siljiydi
-
Mos keladigan qo'shimchani topish
o
agar 1 yoki
undan ortiq belgi mos kelsa,
shablon bu
qo'shimchaning birinchi mos kelishiga qadar o'ngga siljiydi
1.
q w t e
e
q e w q r w q w r q r
q w r q
r
2.
q w t e e q
e
r q r
w q w r q r
q
w
