- Bitta matnda bir nechta namunalarni tezkor qidirish
- Xesh funktsiyasidan foydalangan holda sodda pastki qatorli qidiruvda taqqoslashlar sonini kamaytirish (bir turdagi nazorat summasi)
- Xesh funktsiyalari satrlarni (umumiy holatda, ma'lumotlar) raqamli qiymatlarga - deb ataladigan qiymatlarga aylantiradi. hash qiymatlari
- Algoritm R.-K. bir xil xesh funksiyasi bir xil satrlarni bir xil xesh qiymatlariga aylantirishi haqiqatidan foydalanadi
Rabin-Karp algoritmi - 1-qadam
- Biz namunaning chap chetini matnning chap chetiga qo'llaymiz, K = 0
- q va s uchun hq va hs xesh qiymatlarini hisoblang[0…M-1]
- 2-qadam
- Agar hq == hs bo'lsa, u holda q[j] naqsh belgilarini chapdan s[K+j] matn belgilari bilan ketma-ket taqqoslash orqali K-o'rindan boshlab naqshning matnga kiritilganligini tekshiramiz. o'ngga, j=0…M-1
- 3-qadam
- Agar bizda M mos kelsa, u holda matndagi namuna topiladi - ishning oxiri
- Agar K+M >= N bo'lsa, unda namuna matnda topilmadi - ishning oxiri
- Aks holda s[K…K+M-1], K = K+1 uchun hs yordamida s[K+1…K+M] uchun hs ni hisoblang va 2-bosqichga o‘ting.
Rabin-Karp algoritmi int rk_substring_search( const char s[], int N, const char q[], int M) { int k; // matnda namuna ko`chirish int hs = rk_hash(s, M); int hq = rk_hash(q, M); for (k = 0; k < N-M; ++k) { int j; // namuna ko`chirish if (hs == hq) for (j = 0; s[k+j]==q[j]; ++j) if (j == M-1) return k; // topildi // rk_hash_update ishlash vaqti O(1) hs = rk_hash_update(hs, s[k], s[k+M], M); } return -1; // topilmadi} Boyer-Mur algoritmi int Robin_Carp_Matcher(char s[], char q[], int d, int p) {
Do'stlaringiz bilan baham: |
