187
Qidiruv vazifalarida qidiruv satrni ―igna‖ (inglizchadan - "needle")
va qidiruv o'tkaziladigan satrni ―gʻaram‖ (ingliz tilidan - "haystack") deb
belgilash odat tusiga kirgan. Shuningdek, biz qidirish olib boriladigan
alifboni Σ bilan belgilaymiz.
Primitiv algoritmning muvaffaqiyatsizligi.
Agar satrlar birdan
boshlab raqamlangan deb hisoblasak, eng oddiy ―qo'pol kuch‖ (Brute
force) algoritmi (sodda algoritm) quyidagicha boʻladi:
for i=0...|haystack|-|needle|
for j=0...|needle|
if haystack[i+j + 1]<>needle[j]
then goto 1
output("Topildi: ", i+1)
1:
Eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1
taqqoslash;
agar
bir-biriga
o'xshashliklar
ko'p
bo'lsa,
tezlik
O(|haystack|·|needle|) ga tushadi.
Primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani
isbotlangan.
Bugungi kunda qismiy satrlarni qidirish algoritmlarining xilma-
xilligi mavjud. Dasturchi bunday omillarga qarab, mosini tanlashi kerak.
1.
Optimallashtirish kerakmi yoki primitiv algoritm yetarlimi?
Jimlik boʻyicha, bu dasturlash tillarining standart kutubxonalari
amalga oshiradi.
2.
