Knut- Moris- Pratt algoritmlari va ularning dasturlari
![Matnda pattern mos kelmagan holatlardachi?
0-holatdan 1-holatga faqat A bo’lsagina o’tadi. Aks holda 0-holatda qoladi. Demak
tekshirilayotgan birinchi belgi B yoki C bo’lsa, birinchi holatda qoladi.
1-holatdan 2-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatida qoladi, sababi
pattern’ga ko’ra, biz uchun birinchi belgi A bo’lishi kerak. C bo’lsa, 0-holatga qaytadi – qidiruv
patt[0] dan boshlanadi.
2-holatdan 3-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
3-holatdan 4-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatiga qaytadi; C bo’lsa, 0-
holatga qaytadi.
4-holatdan 5-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
5-holatdan 6-holatga faqat C bo’lsagina o’tadi. Agar B bo’lsa 4-holatga qaytadi, sababi 5-
holatga ko’ra, qidiruvda patternning dastlabki 5 belgisi mos kelgan hisoblanadi, ya’ni
qidirilayotgan matnda ABABA allaqachon bor. Keyingi belgi C bo’lishi kerak edi, ammo B
chiqdi (ABABAB). Biz avvalgi mos kelgan harflarni bilar ekanmiz, qidiruvni 0-holatdan emas,
4-holatdan, AB ABAB holatidan davom ettiramiz. A chiqsa, 1-holatga qaytadi.
6-holatga kelganda qidiruv to’xtaydi, biz matn ichidan patternni topgan bo’lamiz.
Yuqoridagi shartlarni graph ko’rinishida ifodalasak:
Jadval ko’rinishida:](https://docx.uz/documents/f9ce4402-faa5-4ecf-b9eb-00fdef2dd88c/page_6.png?v=1)
![AABACA ABABAC AA
6-holatga o’tadi.
Pattern topildi. Qidiruv tugaydi.
Holatlarning o’zgarishini graph va jadvalga qarab boshqatdan ko’rib chiqishingiz mumkin.
Pattern’dan DFAni yasash
Yuqoridagi jadval va graph’ni biz o’zimi ko’rib turib yasadik. Kodda qanday qilib berilgan
pattern’dan DFAni yasaymiz?
DFAni yasashda ikki xil holat bor:
Mos kelish . j-holatida, keyingi belgi c == pattern.charAt(j) bo’lsa, u holda j ni bittaga
oshiramiz.
Mos kelmaslik . j-holatida, keyingi belgi c != pattern.charAt(j) bo’lsa, u holda ohirgi j-1 belgilar
pattern[1..j-1] ichida bo’ladi.
Knuth-Morris-Pratt algoritmini kodda ifodalash](https://docx.uz/documents/f9ce4402-faa5-4ecf-b9eb-00fdef2dd88c/page_8.png?v=1)
![BBBBBBBBBB
A BBBB
A BBBB
A BBBB
A BBBB
A BBBB
A BBBB
Masalan, yuqoridagi holatda ishlash vaqti O((N-M) * M) ga teng.
Rabin-Karp algoritmi
Bizda quyidagi matn bor bo’lsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE
1. patterndagi 0 dan M-1 gacha belgilar bo’yicha hash soni generatsiya qilinadi. Bunda
M – patterndagi belgilar soni.
2. har bir [i..N-1] sikl ichida matndagi i dan M + i – 1 gacha belgilar bo’yicha hash soni
generatsiya qilinadi. Bunda N – matndagi belgilar soni
3. Agar pattern hash va matn substring hash bir-biriga teng bo’lsa, pattern matn
ichidan topilgan hisoblanadi.
Hash sonini generatsiya qilishning eng tezkor, oson usullardan biri – pattern’ning har bir
belgisi kodini olib, ularni birlashtirish va uni biror katta tub songa bo’lib, qoldig’ini qoldirish
kerak. Javascript da bu ish quyidagicha bajariladi:
const primeNumber = 997 // tub son
const pattern = "NEEDLE" // qidiriladigan so'z
const hash = pattern.split('').map(char => char.charCodeAt()).join('') %
primeNumber
// pattern uchun hash soni 769
Demak bizda patternning hash soni generatsiya qilindi. Endi uni matndagi har bir i dan M + i –
1 gacha substring’lardan hash son generatsiya qilib uni pattern’ning hash soniga solishtirib
chiqiladi. Substring uchun ham, pattern uchun ham bir xil usulda hash generatsiya qilinadi.
FINDINAHAYSTACKNEEDLEINA
FINDIN // 5 != 769](https://docx.uz/documents/f9ce4402-faa5-4ecf-b9eb-00fdef2dd88c/page_13.png?v=1)
![INDINA // 877 != 769
NDINAH // 105 != 769
DINAHA // 259 != 769
INAHAY // 541 != 769
NAHAYS // 414 != 769
AHAYST // 271 != 769
HAYSTA // 963 != 769
AYSTAC // 805 != 769
YSTACK // 535 != 769
STACKN // 507 != 769
TACKNE // 178 != 769
ACKNEE // 98 != 769
CKNEED // 615 != 769
KNEEDL // 317 != 769
NEEDLE // 769 == 769
Juda oddiy va mohirona usul!
Yuqoridagi hash generatsiya qilish usuli split() va join() metodlari ishlatilgani sababli sekinroq
ishlashi mumkin. Shuning uchun biz hash generatsiya qilishni sinalgan usul – Horner
metodi yordamida amalga oshiramiz. Umumiy formula quyidagicha:
x
i = ( t
i * R M-1
+ t
i+1 * R M-2
+ … + t
i+M-1 * R 0
) % Q
Bu yerda:
x
i – matndagi [i..M + i – 1] substring uchun hash soni.
t
i – str.charCodeAt(i) – matn/pattern belgisining ASCII jadvalidagi raqami.
R – radix soni. ASCII uchun 128 yoki 256.
M – patterndagi belgilar soni.
Q – tub son.
Hash funksiya kodi:
function hornerHash (str, M) {](https://docx.uz/documents/f9ce4402-faa5-4ecf-b9eb-00fdef2dd88c/page_14.png?v=1)
Knut- Moris- Pratt algoritmlari va ularning dasturlari