Urganch davlat universiteti axborot texnologiyalari kafedrasi

for i:=

2 

to m do begin 

  while (k>

0

) 

and (patt[i]<>patt[k+

1

]) 

do 

    k:=f[k]; 

   

if patt[i]=patt[k+

1

] 

then inc(k); 

   f[i]:=k 

end;

 

 

Ushbu  algoritm  bo‘yicha  bajaraladigan  simvollar  taqqoslashining  umumiy  miqdorini 

baholaymiz.  While  sikli  tanasining  bajarilishlari  uning  mos  keluvchi 

m

i

,...

2



qiymatlarida 

miqdorini w(i) orqali belgilaymiz. Takidlaymiz, while sikl tanasining bajarilishi k qiymatni 1 dan 

kichik bo‘lmagan qiymatiga kamaytiradi. Bu yerdan. 

 

Bo‘lsa 

  

i ning har bir qiymatida simvollarning taqqoslanishi sikl tanasi bajarilishlaridan 2 ga ko‘p 

ro‘y beradi ulardan bittasi sikl sarlavhasidagi shartni hisoblaganda qo‘shimcha ravishda va yana 

bittasi  tarmoqlanish  operatorida.  Bu  yerdan  simvollar  taqqoslanishlarining  umumiy  miqdori  3 

(m-1)  dan  kata  emasligi,  ya`ni  m  ga  to‘g‘ri  proporsional  ekanligi  kelib  chiqadi.  Shunday  ekan 

qaytishlar  funksiyasi  tuzilganida  simvollar  taqqoslanishlarining  umumiy  miqdori  (namuna 

uzunligiga  nisbatan)  chizili 

  bahoga  ega.  Masala  yechilishining  algoritmi  prosedura 

ko‘rinishida amalga oshiramiz  (2.6 listing).  Namuna  aChar=array[1..255] of char  tipidagi patt 

massivida, f qaytishlar funksiyasi aPos=array[1..255] of byte tipidagi f massivida qaytish tadqiq 

etilgan  massivda  va  namunada  joriy  pozitsiyalar  raqamlarning  tp  va  pp  o‘zgaruvchilarda 

saqlaydi.  Izlash  boshlangandan  oldin  ular 0  ga  teng.  Matnning  navbatdagi  simvoli  patt  [pp+1] 

bilan  taqqoslanuvchi  s  o‘zgaruvchiga  kiritiladi.  Kiruvchi  fin  va  chiquvchi  fout  fayllarning 

oldindan mos keluvchi boshlang‘ich holatlarga o‘tkazilgan deb tahmin qilinadi.  

2.6-matnning KMP metodi bo‘yicha matnda qator ostining barcha kirishlarini izlash