pp:
byte
;
tp:
longint
;
Begin
pp:=
0
;tp:=
0
;
while
true
do begin
if eof(fIn)
then
break
;
read(fIn,c); inc(tp);
while (pp>
0
)
and (patt[pp+
1
]<>c)
do
pp:=f[pp];
if patt[pp+
1
]=c
then inc(pp);
if pp=m
then begin
write(fOut,
' '
,tp-m+
1
);
pp:=f[pp];
end
end;
end;
Yechimning
tahlili.
Endi
keltirilgan
prosedura
bajarilganda
simvollar
taqqoslanishlarining miqdorini baholaymiz. Ta’kidlaymiz: tashqi tp sikl tanasining har bir
bajarilishida 1 ga kattalashadi, pp da esa 1 ga kattalashadi va f[pp] ning ozlashtirilishini hisobiga
hech bo‘lmasa minimum 1 ga kamayishi mumkin. Navbatdagi tp(1 dan n gacha ) qiymatida pp
ning boshlang‘ich qiymatini b(tp) orqali, w(tp) orqali esa matndagi tp ning bir va aynan bir
pozitsiyasida pp kamayishlarining miqdorini belgilaymiz.
U jolda tp>1 da b(tp) b(tp-1)-w(tp)+1,
Bu yerdan w(tp) b(tp-1)- b(tp)+1.
Demak ,
W(1)+w(2)+….w(n)
1+b[1]-b[2]+1++b[2]-b[3]+1+…+b[n-1]-b[n]+1= n + b[1]-b[2]
n+1.
Algoritmni amalga oshirishdan ko‘rinib turibdiki, tp ning har bir qiymatida, agarda {*}
siklning bajarishlarini hisobga olmasa ularning har biri yana bitta taqqoslashni qo‘shganida,
simvollar ikki martadan ko‘p bo‘lmagan miqdorda taqqoslanadi. Biroq tp n-1 marta ortadi, {*}
siklini bajarilishining umumiy miqdori esa, ya’ni pp qiymatlarning kamayishi n+1 dan ko‘p
bo‘lmagan marta, shuning uchun taqqoslashlarning umumiy soni 2n-2+n+1 dan ko‘p bo‘lmagan
marta o‘zgaradi, ya’ni O(n) bahoga ega bo‘ladi. Matnning har bir simvolli aqalli bir marta
taqqoslansa O(n) bahoni olamiz. Qaytishlar funksiyasini hisobga olgan holda quyidagi xulosa
keltiramiz: uzunligi n matnga uzunligi m namunaning barcha kirishlarining izlanishining ushbu
amalga oshirishi simvollarning
taqqoslanishni talab etadi. Summar qiyinchilik
taqqoslashlar miqdoriga to‘g‘ri proparsional, shuning uchun qiyinchilikning umumiy bahosi
ham
hisoblanadi.
Eslatma. KMP algoritmi eng yomon holda ham chiziqli qiyinchilikni ta’minlaydi, biroq
o‘rtachasini olganda u samarali hisoblanadi. Yomon xollarda kvadratik baholashga ega bo‘lgan
boshqa algoritmlar ham mavjud, biroq o‘rtachasini olganda KMP algoritmiga qaraganda tezroq
ishlaydi ( taxminan 2-3 marta). Boshqa g‘oyalarga asoslangan bu algoritmlar [39] da, esa bittasi
[22] da kengroq keltirilgan. Bir o‘lchamli amalga oshirish uchun ular yaroqli emas.
Masalan yechilishning to‘liq dasturi yozilsin.
Masalani namunalar bir necha, masalan, 1 dan 20 gacha, bo‘lgan hol uchun yechish.
Ko‘rsatma har bir namuna uchun qaytishlar funksiya tuzilsin va uning qiymati navbatdagi
simvoliga qaralsin. Masalan namunaning matnga navbatdagi kirishi faqat oldingining tugashidan
keyin boshlanishi mumkin bo‘lgan hol uchun yechilsin. Masalan aa faqat 1 marta 1 pozitsiyadan
boshlab namuna aa matnga kiradi. Ko‘rsatma: namuna kirishi topilgandan keyin namunadagi
joriy pozitsiyani 0 ga teng deb olish kerak.
Mashqlar
2.1 Uzunligi
katta bo‘lmagan bo‘lmagan longit tipidagi qiymatlar ketma- ketligida
bittadan tashqari barcha qiymatlar juft son marta bittasi esa toq son marta o‘zgaradi. Ushbu
qiymat aniqlansin.
2.2 Kiruvchi matndagi har bir harflarning paydo bo‘lishlarining miqdorini hisoblang.
2.3 Butun n lar qatoridan ko‘paytmalar maksimol bo‘lgan 10 ta sonni tanlang. Kirish
matnnig birinchi qatorida – sonlar miqdori n, 3
keyingi n ta qatorda – integer tipidagi
butun sonlar. Chiqish ixtiyoriy tartibdagi 10 ta son. Agar yechimlar bir nechta bo‘lsa, ulardan
istalgani chiqarilsin.
2.4 2vn ta musbat sonlar berilgan bo‘lib ularni juftlarga shunday ajratish mumkinki,
ularning simvollari bir hil son bo‘ladi. Bu sonlarni juftlashlardagi ko‘paytmalari bir xil
bo‘ladigan juftliklarga ajratish mumkinligi aniqlansin.
Kirish. Matning birinchi qatori n ta sondan iborat (1
keyingi n qatorlarda
n
a
a
a
...
..........
,
2
1
natural son berilgan .
Chiqish: agar izlanayogan ajratilshi mavjud bo‘lsa 1, aks holda 0.
2.5 Matnda longit tipidagi natural sonlar ketma-ketligi yozilgan.
a) Ma’lumki undagi qandaydir son, qolganlari hammasi birga olingan holdagiga
qaraganda ham, ko‘proq uchrashadi ushbu son topilsin .
b) Undagi qandaydir son, qolganlari hammasi birga olingan holdagiga qaraganda ham
ko‘proq, uchrashadi deb taxmin qilinadi. Shundaymi yoki yo‘qligi aniqlansin, agar shunday
bo‘lsa shu son topilsin.
2.6 Mijozlar sartorashga kelishadilar, agar navbat bo‘lsa navbat oladilar va tartibda soch
oladiradilar. Mijoz sochini olib bo‘lgan usta keyingisining sochini olishga tayyor bo‘ladi. Har bir
mijoz uchun uning sochini oilsh t vaqti ma’lum: mijoz soch olish boshangandan t vaqt o‘tgach
ketadi.
Kirsh: Matnning birinchi qatorida –mijozlar miqdori
)
10
1
(
6
m
m
. Navbatdagi t
qatorda butun musbat sonlar juftigi yozilgan. –Mijozning kelish payti va uning soch oldirish
vaqti. Kelish paytlari vaqtning boshlang‘ich momentiga nisbatan berilgan va kamaytirilmaydigan
ketma-ketlikni shakllantirmaydi. Ketish mamentlari aniqlansin.
2.7 Musbat butun sonda raqamni shunday o‘chirish kerakki, qolgan son iloji boricha katta
son bo‘lsin. Kirish va Chiqish: sonli matn qator uzunligi 10
5
dan katta emas. Masalan, 321
kirishga 32 chiqish, 123 ga -23 chiqish mos keladi.
2.8 Matnda probellar va punktuatsiya belgilari bilan ajratilgan alfavitdagi a,…,z
harflardan tuzilgan so‘zlar ihtiyoriy miqdorda tuzilgan. So‘zlar qatordan qatorga bo‘lib
o‘tkazilmaydi. Punktuatsiya belgilari –
"
,
"
,
"
"
,
"
;
"
,
":"
Bir letirli so‘zlarni, ortiqcha probellarni va
punktuatsiya belgilarini yo‘q qiluvchi matanni son qiluvchi dastur yozilsin.
2.9 Matnda 0 va 1 simvollar mavjud bo‘lib, ularning ketma-ketligi matnning qatorlarga
ajratilishiga qaramasdan uzluksiz hisoblanadi. Uzunligi 1000 dan katta bo‘lmagan alohida
qatorlarda berilgan 0 va 1 dan iborat namunalar matnda mavjudmi yoki aniqlash dasturi yozilzin.
Masalan 00 va 11 qatorlar bilan shakllantirilgan matnda 001 va 011 namunalar mavjud va 10 va
111 namunalar mavjud emas.
Kirish: potterns.txt matnning birinchi qatorida
i miqdorda namunalar (1 dan 20 gacha )
mavjud. Navbatdagi uzunligi 1000 dan katta bo‘lmagan n ta qatorda namunalar mavjud. text.txt
matnning
9
10
2
dan ko‘p bo‘lmagan qatorlari 1000 dan katta bo‘lmagan uzunlikka ega va 0 va 1
dan iborat ketma-ketlikka ega. Undagi namunalarning kirishi topilsin.
Chiqish: namunalarga mos keluvchi qatorlarning ketma-ketligi. Agar namuna matnga
kirmasa, qatorda 0 simvoli, aks holda 1 simvoli va ikkita butun son- matndagi qatorning raqami
va namuna matnga kiradigan qatordagi pozitsiya raqami yoziladi. Masalan, yuqorida ko‘rsatilgan
matn qatori va namunalar uchun birinchi qatorda 11, ikkinchi qatorda -12, uchinchi va to‘rtinchi
qatorda 0 bo‘ladi.
