Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

196 
Simvol 
q 
w 
r 
e 
t 
Oxirgi pozitsiya 
4 
2 
3 
0 
0 
1.
 
q t e e q r 
w
 q w r e e 
q w r q 
r
 
2.
 
q t e e q r 
w
 q w r e e 
q 
w
 r q r 
 
Suffiks jadvali. 
Mumkin bo'lgan barcha qo'shimchalar uchun 
jadvalda qismiy satrni o'zgartirish kerak bo'lgan eng kichik miqdor 
ko'rsatilgan, u yana qo'shimchaga mos keladi. Agar bunday siljishning 
iloji bo'lmasa, satrning uzunligi ko'rsatilgan. 
Misol. Qismiy satr: qwrqr 
Suffiks 
Boʻsh 
r 
qr 
rqr 
wrqr 
qwrqr 
qadam 
1 
2 
5 
5 
5 
5 
1.
 
q t e e q r 
w
 q w r e e 
q w r q 
r
 
2.
 
q t e e q r 
w
 q w r e e 
q 
w
 r q r 
3.
 
q t e e q r w q 
w
 r e e 
q w r 
q
 r 
4.
 
q t e e q r w q w 
r
 e e 
q w 
r 
q r 
 
Algoritmning murakkabligi. 
O (| haystack | + | needle | + | Σ |) 
davriy bo'lmagan qismiy satrlar bo'yicha 
O (| haystack | · | needle | + | Σ |) davriy
haystack - berilgan satr, needle – qismiy satr, Σ - solishtirish uchun 
alifbo 

197 
1991-yilda Koul shuni ko'rsatdiki, davriy bo'lmagan sxemalar 
bo'yicha, algoritm satr bo'ylab to'liq o'tishda 3·|haystack| tadan ko'p 
bo'lmagan taqqoslashni amalga oshiradi. 
 
Boyer-Mura algoritmi (C++) 
#include  
using namespace std; 
# define NO_OF_CHARS 256 
 
 
void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS]) 
{ 
 
int i; 
 
for (i = 0; i < NO_OF_CHARS; i++) 
 
 
badchar[i] = -1; 
 
for (i = 0; i < size; i++) 
 
 
badchar[(int) str[i]] = i; 
} 
void search( string txt, string pat) 
{ 
 
int m = pat.size(); 
 
int n = txt.size(); 
 
int badchar[NO_OF_CHARS]; 
badCharHeuristic(pat, m, badchar); 
 
int s = 0;
 
while(s <= (n - m)) 
 
{ 
 
 
int j = m - 1; 
 
 
while(j >= 0 && pat[j] == txt[s + j]) 
 
 
 
j--; 
 
 
if (j < 0) 
 
 
{ 
 
 
 
cout << s << endl; 
 
 
 
s += (s + m < n)? m-badchar[txt[s + m]] : 1; 
 
 
} 
 
 
else 
 
 
 
s += max(1, j - badchar[txt[s + j]]); 
 
} 

198 
} 
int main() 
{ 
 
string txt= "ABAAABCD"; 
 
string pat = "ABC"; 
 
search(txt, pat); 
 
return 0; 
} 
Mavzu yuzasidan savollar: 
1. Qismiy satrlarni izlash algoritmi nima? 
2. Qismiy satrlarni izlash algoritmlarini foydalanish samaradorligini 
taqqoslang 
3. Suffiks jadvali nima?
4. Satrlar uchun xesh funksiyasini qoʻllang 
5. Robin-Karp va Boyer-Mur algoritmlarini taqqoslang? 
Mustaqil ishlash uchun masalalar: 
1. C++ tilida xesh jadvallarni hosil qiling.
2. C++da xesh jadvallarning metodlarini qoʻllang 
 
 

199 
GLOSSARY 
Abstrakt ma‟lumotlar turi (ADT – Abstract Data Type)
- bu 
ma‘lumotlar turlari uchun matematik model, bu yerda ma‘lumotlar turi 
xatti-harakatlari (semantikasi) bilan foydalanuvchi nuqtai nazaridan 
aniqlanadi 
Algoritm
- bu belgilaydigan cheklangan qoidalar toʻplami, muayyan 
vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi va beshta 
muhim xossaga ega: aniqlik, tushunarlilik, kiritish, chiqarish, 
samaradorlik 

Download 4,61 Mb.