Mavzu : matnda qidiruv algoritimini tahlil qilish

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

To’liq codi:
JavaScript: