Bizda quyidagi matn bor bo’lsin

MURAKBAKLIK:
Rabin-Karp algoritmining o'rtacha va eng yaxshi ish vaqti O(n+m) , lekin uning eng yomon vaqti O(nm) dir . Rabin-Karp algoritmining eng yomon holati naqsh va matnning barcha belgilari txt[] ning barcha pastki qatorlari xesh qiymatlari bilan pat[] ning xesh qiymatiga mos kelganda yuzaga keladi. Masalan, pat[] = "AAA" va txt[] = "AAAAAAA".
ALGORITM :







RABIN-KARP-MATCHER (T, P, d, q)
1. n <- uzunlik [T]
2. m <- uzunlik [P]
3. h <- d ^m-1 mod q
4. p <- 0
5 t ₀ <- 0
6. i <- 1 dan m gacha
7. do p <- (dp + P[i]) mod q
8. t ₀ <- (dt ₀ +T [i]) mod q
9. s <- 0 dan nm gacha
10. bajaring agar p = t _s
11. keyin P [1.....m] = T [s+1.....s + m]
boʻlsa 12. u holda “Naqsh paydo boʻladi. siljish bilan" s
13. Agar s < nm
14. u holda t _s+1 <- (d (t _s -T [s+1]h)+T [s+m+1])mod q

DASTUR :







#include
nom maydoni std yordamida;

// d - kirish alifbosidagi belgilar soni #define d 256 bekor qidiruv ( char pat[], char txt[], int q) { int M = strlen (pat); int N = strlen (txt); int i, j; int p = 0 ; // naqsh uchun xesh qiymati int t = 0 ; // txt uchun xesh qiymati int h = 1 ;

// (i = 0; i < M - 1; i++) h = (h * d) % q

uchun h qiymati "pow(d, M-1)%q" bo'ladi ; // (i = 0; i < M; i++) { p = (d * p + pat[i]) % q uchun naqsh va birinchi // matn oynasining xesh qiymatini hisoblang ; t = (d * t + txt[i]) % q; } // (i = 0; i <= N - M; i++) uchun naqshni matn ustida birma-bir siljiting { // Matnning joriy oynasining xesh qiymatlarini tekshiring // va naqsh. Agar xesh qiymatlari mos kelsa, faqat // belgilarni bittadan tekshiring if ( p == t ) {











/* Belgilarni birma-bir tekshiring */
uchun (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break ;
}

// agar p == t va pat[0...M-1] = txt[i, i+1, ...i+M-1]
if (j == M)
cout<<"Naqsh topilgan indeksida "<< i<}

// Matnning keyingi oynasi uchun xesh qiymatini hisoblang:
// yetakchi raqamni olib tashlang,
agar ( i < NM )
{
t = (d*(t - txt[i]*h) + txt[i+M] boʻlsa, keyingi raqamni qoʻshing. )%q;

// t ning manfiy qiymatini olishimiz mumkin, uni
// musbatga
aylantirsak (t < 0)
t = (t + q);
}
}
}

/* Haydovchi kodi */
int main()
{
char txt[] = "SALOM YIGITLAR BU SALOM DUNYONI BOSIDI" ;
char pat[] = "SAlom" ;
int q = 101 ; // tub sonlarni
qidirish (pat, txt, q);
qaytish 0 ;
}



Chiqish:
0 indeksida
topilgan naqsh 23 indeksda topilgan naqsh

Mavzular