Algoritm haqda tushuncha

3)Knut-Morris-Pratt algoritmi va uning murakkabligi


Matn ichida qidiruv uchun brute-force yondashuvining kamchiligi – pattern’dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boshqatdan boshlashi kerak. Shuning uchun worst case O(N*M) bo’lib ketadi. Misol uchun, bizda matn A B A A A A B A A A A A A A A A bo’lsin. Pattern esa BAAAAAAAAA.
Qidiruv jarayoni:
A B A A A A B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
B A A A A A A A A A
E’tibor bergan bo’lsangiz, ikkinchi siklda patternning 6-belgisi mos kelmay qoldi. Demak biz text’dagi biz ko’rib o’tgan ohirgi 6 belgi BAAAAB ekanini bilamiz. Nima uchun qidiruvni yana boshqatdan boshlashimiz kerak? 3-6 sikllarni tushirib qoldirib, 7-sikldan davom ettirishning imkoni bormi?
Knuth-MorrisPratt (KMP) algoritmi mana shu muammoga yechim sifatida kelib, qidiruvni boshqatdan boshlamaslikning imkonini beradi. U Deterministic Finite Automaton g’oyasiga asoslangan.
Deterministic Finite Automaton
Deterministic finite automaton (DFA) – kompyuter nazariyasida (computer science) abstrakt string qidiruvchi mashina. U holatlarning aniq bir to’plami bo’lib, berilgan (yoki tekshirilayotgan) input qiymatiga qarab, bir holatdan ikkinchi holatga o’tishi mumkin. U asil holatdan boshlanib, ohirgi holatga yetganda tugaydi.
Oson misol bilan tushuntirishga harakat qilaman. Bizda quyidagi ro’yhat bor:
[ 'A', 'AA', 'BAC', 'DBCA', 'AFAB', 'AWAVABBBB', 'ABABAB', 'GAAAA', 'FRBABA', 'AJECB' ]
Biz ular ichidan A dan boshlanadiganlarini topishimiz kerak.
Shart asosida DFAni yasaymiz. Shartga ko’ra, stringning birinchi belgisi A bo’lishi kerak, shunda keyingi belgilarni tekshirishni davom ettiradi. Aks holda dastlabki holatda qoladi.

Ro’yhatdan stringlarni tekshirib chiqamiz:
A. 0 holatdan 1 holatga o’tdi. Qidiruv yakunlandi. 1 holatga o’tgani uchun string topilgan hisoblanadi.