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
