Dynamic programming

Dynamic programming (DP, dinamik dasturlaş) deb muammoni kiçik masalalarga ajratib, ularni faqat bir marta yeçiş va natijani keyingi bir xil tipdagi masalada işlatiş uçun saqlab turiş texnikasiga aytiladi.
Dasturchi, frilanser, gik va introvert

Dynamic programming (DP, dinamik dasturlaş) deb muammoni kiçik masalalarga ajratib, ularni faqat bir marta yeçiş va natijani keyingi bir xil tipdagi masalada işlatiş uçun saqlab turiş texnikasiga aytiladi.

NFA simulyatsiyasini körib çiqişdan avval NFAning özini kodda qanday ifodalaşni körib çiqamiz. Avvalgi maqolada aytib ötilganidek, NFAda 0 dan M gaça state'lar + accept state mavjud. M - bu yerda qavs içiga olingan regular expression'dagi belgilar soni. Masalan ((A*B|AC)D) regexp uçun NFA state'lari

Regular Expression algoritmiga ötişdan avval NFA - Nondeterministic Finite Automaton abstrakt hisoblaş maşinasi haqida tanişib çiqiş kerak böladi.

Regular expression (yana regex, regexp) - qidiriş patternini belgilab beruvçi belgilar ketma-ketligi. Odatda regex'lar matn içida qidiruv algoritmlarida sözlarni topiş (find), topiş va almaştiriş (find & replace), hamda kiritilgan ma'lumotni tekşiriş uçun işlatiladi.

Matn içida qidiruv uçun yana bir diqqatga molik algoritmlardan biri - Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning işlaş tartibini batafsil tuşuntirişga harakat qilaman.

Avvalgi mavzuda ötganimiz - Knuth-Morris-Pratt algoritmi yordamida biz matn içida qidiruvni O(N + M) vaqt içida bajara olamiz. Navbatdagi algoritm - Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq işlaydi. Örganişga ham osonroq ;)

Matn içida qidiruv uçun brute-force yondaşuvining kamçiligi - pattern'dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boşqatdan boşlaşi kerak. Şuning uçun worst case O(N*M) bölib ketadi.
Matn içida söz/ibora qidiruv (substring search) algoritmlari bilan tanişib çiqişni boşlaymiz. Qöyiladigan masala juda oddiy. N uzunlikdagi matn içidan M uzunlikdagi iborani (pattern) topiş kerak bölsin. Bunda matn juda katta hajmda, pattern esa juda kiçik - bir-ikki sözdan iborat.

Uşbu maqolada biz ba'zi string amallarini R-way trie ma'lumot tuzilmasida körib ötamiz.

Ternary search tries (TST, uçlamçi qidiruv trie) R-way tries'dagi kamçilikka yeçim ölaroq tavsiya etiladi. TSTda belgilar indeks körinişida emas, node içida saqlanadi (R-way tries'da belgilar indeks nomer sifatida saqlanardi). Şuningdek har bir node uç çild'ga ega: kiçikroq (çap), teng (örtada), kat