Satr algoritmlari

String ustidagi masalalar algoritmik muammolar ichida eng ko'p uchraydigan toifadan. Sababi oddiy: foydalanuvchidan keladigan ma'lumotlarning katta qismi avval matn shaklida bo'ladi. Qidiruv so'rovi, forma maydoni, elektron pochta, fayl nomi, URL, loglar — hammasi avval string. Shu sababli string ustida samarali ishlay bilish dasturlashda juda muhim ko'nikma.

String masalalarini hal qilishda ko'p hollarda murakkab maxsus algoritmlar shart emas. Aksariyat masala bir nechta asosiy texnika yordamida samarali hal qilinadi: ketma-ket yurish, ikki ko'rsatkich, siljuvchi oyna va belgilar chastotasini hisoblash. Bu texnikalar individual holda oddiy ko'rinadi. Asosiy mahorat esa yangi masalada qaysi texnikaning mos ekanini tez taniy bilishda.

Traversal: har bir belgini ko'rib chiqish

Traversal — belgilarni stringning boshidan oxirigacha ketma-ket ko'rib chiqish. Bu string ustidagi eng sodda va eng ko'p ishlatiladigan texnika. Masalaning tabiatiga qarab ko'rsatkich oldinga ham, orqaga ham yurishi mumkin, lekin klassik holatda chap tomondan o'ngga qarab harakat qilinadi.

string = "dasturlash"

i = 0 → 'd'
i = 1 → 'a'
i = 2 → 's'
i = 3 → 't'
i = 4 → 'u'
i = 5 → 'r'
i = 6 → 'l'
i = 7 → 'a'
i = 8 → 's'
i = 9 → 'h'

Har bir belgida biror tekshiruv yoki hisob-kitob bajariladi. Tsikl bitta o'zgaruvchi — pozitsiya ko'rsatkichi — bilan boshqariladi.

FUNCTION traversal(s):
    i = 0
    WHILE i < s.length:
        s[i] belgisi bilan biror amal bajar
        i = i + 1

Traversal quyidagi vazifalar uchun mos:

• string ichida biror belgini qidirish;
• har bir belgining chastotasini hisoblash;
• bir stringni boshqa stringga aylantirish;
• ikkita stringni belgima-belgi solishtirish;
• string to'g'ri formatda yozilganini tekshirish.

Vaqt murakkabligi: O(n) — n uzunlikdagi string uchun har bir belgi bir marta ko'riladi.

Xotira murakkabligi: O(1) — agar natija uchun qo'shimcha joy ajratilmasa. Natija alohida saqlanishi kerak bo'lsa, ajratiladigan joyga qarab o'zgaradi.

Ikki ko'rsatkich: bir vaqtda ikki joyni kuzatish

Ikki ko'rsatkich (two pointers) texnikasida string ichida bir vaqtda ikkita pozitsiya kuzatiladi. Bu pozitsiyalar masala turiga qarab turli strategiya bilan siljishi mumkin.

Qarama-qarshi tomondan yaqinlashish

Eng keng tarqalgan holat — bir ko'rsatkich boshidan, ikkinchisi oxiridan harakatlanib, markazga tomon yaqinlashadi:

string = "d a s t u r l a s h"
indexes:  0 1 2 3 4 5 6 7 8 9
          ^                 ^
          l                 r

l o'ngga, r chapga siljiydi. Ular uchrashgunga yoki o'tib ketgunga qadar — ya'ni l < r shart bajarilgunga qadar — davom etadi.

FUNCTION ikki_ko'rsatkich_qarama_qarshi(s):
    l = 0
    r = s.length - 1

    WHILE l < r:
        s[l] va s[r] bilan biror amal bajar
        l = l + 1
        r = r - 1

Bu texnika quyidagi muammolarga mos:

• string palindrommi ekanini tekshirish;
• stringni joyida teskari aylantirish;
• belgilarni ko'rsatkichlar asosida almashtirish;
• tartiblangan stringda ikki qiymatning yig'indisini topish.

Vaqt murakkabligi: O(n) — ikkala ko'rsatkich birlashib, har bir belgini ko'pi bilan bir marta ko'radi.

Xotira murakkabligi: O(1) — faqat ikki pozitsiya saqlanadi.

Bir yo'nalishda, turli rolda

Ikkinchi holat — ikkala ko'rsatkich ham chapdan o'ngga harakat qiladi, lekin birining vazifasi boshqasidan farq qiladi. Ko'pincha biri "yozish joyi", ikkinchisi "o'qish joyi" rolini bajaradi:

string = "a a b b c"
          ^
         yozuvchi
              ^
             o'quvchi

Bu holat quyidagi muammolarda uchraydi:

• takroriy belgilarni o'chirish (in-place);
• ma'lum shartni qanoatlantiradigan belgilarni oldinroqqa siljitish;
• zichlashtirish yoki filtrlash amallarida.

Siljuvchi oyna: harakatlanuvchi oraliq

Siljuvchi oyna (sliding window) texnikasida stringning ma'lum bir uzluksiz oralig'i — "oyna" — o'ngga siljib boradi. Oyna ichidagi belgilar to'plami bir vaqtda tahlil qilinadi.

string = "a b c d e f"
          [a b c]
            [b c d]
              [c d e]
                [d e f]

Bu yerda uch belgili oyna chapdan o'ngga siljidi. Har bir holatda oyna ichidagi qism ko'riladi.

Qat'iy o'lchamli oyna

Oyna hajmi masala shartidan oldindan ma'lum. Masalan, "uzunligi k bo'lgan qismning maksimal yig'indisini top" degan masalada oyna hajmi k — u kengaymaydi ham, toraymaydi ham, shunchaki siljib boradi.

FUNCTION qatiy_oyna(s, k):
    oyna yig'indisini hisoblash (birinchi k belgi)

    i = k
    WHILE i < s.length:
        yangi belgini oynaga qo'sh
        eng chap belgini oynadan chiqar
        natijani yangilash
        i = i + 1

O'zgaruvchan o'lchamli oyna

Oyna hajmi shartga qarab kengayadi yoki torayadi. Shart buzilguncha oyna o'ng tomondan kengayadi. Shart buzilganda chap tomoni torayadi va shart qayta bajarilgunga qadar torayish davom etadi.

FUNCTION ozgaruvchan_oyna(s):
    l = 0
    natija = 0

    r = 0
    WHILE r < s.length:
        s[r] ni oynaga qo'sh

        WHILE shart buzilgan:
            s[l] ni oynadan chiqar
            l = l + 1

        natijani yangilash (masalan, r - l + 1)
        r = r + 1

    RETURN natija

O'zgaruvchan oynada "shart" nimaga qarab belgilanishini masalaning o'zi ko'rsatadi. Masalan, "takroriy belgi yo'q" shartida belgilar to'plami saqlanadi.

Vaqt murakkabligi: O(n) — har bir belgi oynaga eng ko'pi bilan bir marta kiradi va bir marta chiqadi. Jami 2n qadam, ya'ni O(n).

Xotira murakkabligi: O(k) — k oyna ichidagi noyob belgilar soni. Chegaralangan alfavitda (masalan, faqat kichik ingliz harflari) bu O(1) hisoblanadi.

Note

Siljuvchi oyna masalasini tanib olish uchun asosiy belgi: masala stringning uzluksiz bo'lagiga (substring) tegishli va uni maksimallashtirish yoki minimallashtirilish kerak. Bu ko'rinsada, siljuvchi oyna texnikasini sinab ko'rish kerak.

Belgilar chastotasi: harf necha marta uchraydi?

Ko'plab string masalalarida "bu belgidan nechta bor?" degan savol kelib chiqadi. Buning uchun belgilar chastotasini saqlaydigan jadval qo'llanadi.

Faqat kichik ingliz harflari ishlatiladigan masalada 26 ta katakli massiv yaratiladi. Har bir katakka mos harfning necha marta uchragani saqlanadi:

string = "dasturlash"

d → 1
a → 2
s → 2
t → 1
u → 1
r → 1
l → 1
h → 1

Agar belgilar to'plami chegarasiz yoki oldindan noma'lum bo'lsa (masalan, har qanday Unicode belgi bo'lishi mumkin), lug'at (hash map) ishlatiladi: kalit — belgi, qiymat — chastota.

FUNCTION chastota_hisoblash(s):
    jadval = bo'sh lug'at

    i = 0
    WHILE i < s.length:
        belgi = s[i]
        IF belgi jadvalda mavjud:
            jadval[belgi] = jadval[belgi] + 1
        ELSE:
            jadval[belgi] = 1
        i = i + 1

    RETURN jadval

Chastota jadvali quyidagi muammolarda foydali:

• ikkita string anagrammi ekanini tekshirish;
• eng ko'p uchraydigan belgini topish;
• siljuvchi oyna ichidagi shartni kuzatish;
• bir stringdagi barcha belgilar boshqasida ham bormi degan tekshiruv.

Vaqt murakkabligi: O(n) — string bir marta ko'rib chiqiladi.

Xotira murakkabligi: O(k) — k noyob belgilar soni. Chegaralangan alfavitda O(1).

Substring qidirish

Stringning ichida boshqa bir string (pattern) mavjudligini tekshirish — keng tarqalgan vazifa. Matn muharririda qidiruv, URL ichidan parametrni ajratish, log qatorida xato kodini topish — bularning barchasi substring qidirish masalasi.

Sodda yondashuv: har bir pozisiyadan boshlab pattern mosligini tekshirish.

FUNCTION substring_qidirish(matn, pattern):
    n = matn uzunligi
    m = pattern uzunligi

    i = 0
    WHILE i <= n - m:
        j = 0
        WHILE j < m AND matn[i + j] == pattern[j]:
            j = j + 1

        IF j == m:
            RETURN i   // topildi

        i = i + 1

    RETURN -1   // topilmadi

Vaqt murakkabligi: O(n * m) — n matn uzunligi, m pattern uzunligi. Har bir pozisiyada m belgini tekshirish kerak bo'lishi mumkin.

Kichik matinlarda bu yetarli. Lekin juda uzun matnlarda yoki pattern ham uzun bo'lsa, KMP, Rabin-Karp yoki Boyer-Moore kabi algoritmlar O(n + m) vaqtda ishlaydi. Bu algoritmlar pattern ichidagi takrorlanuvchi tuzilmadan foydalanib, ortiqcha tekshirishlarni qisqartiradi. Ular alohida mavzu sifatida o'rganiladi.

Qaysi texnikani tanlash kerak?

Masalani o'qiganda quyidagi savollar texnikani tanlashda yordam beradi:

"Barcha belgilarni birin-ketin ko'rish kerakmi?" → Traversal.

"Stringning ikkita pozitsiyasini bir vaqtda ko'rish kerakmi?" → Ikki ko'rsatkich.

"Stringning uzluksiz bir bo'lagini ko'rib, uni maksimallashtirish yoki minimallashtirishim kerakmi?" → Siljuvchi oyna.

"Belgilar necha marta uchraydi, barcha kerakli belgilar bormi?" → Belgilar chastotasi.

"Bir string boshqaning ichida bormi yoki qayerda?" → Substring qidirish.

Ko'p masalada bu texnikalar birlashtiriladi. Masalan, siljuvchi oyna bilan belgilar chastotasini birgalikda ishlatish juda keng tarqalgan.

Vaqt va xotira murakkabligi jadvali

Texnika	Vaqt murakkabligi	Xotira murakkabligi
Traversal	O(n)	O(1)
Ikki ko'rsatkich	O(n)	O(1)
Siljuvchi oyna	O(n)	O(k)
Belgilar chastotasi	O(n)	O(k)
Sodda substring qidirish	O(n × m)	O(1)

k — noyob belgilar soni. Chegaralangan alfavitda sabit bo'lgani uchun O(1) ham deyiladi.

Keng tarqalgan xatolar

Siljuvchi oynada chegara shartini noto'g'ri yozish

l < r o'rniga l <= r yoki r < n o'rniga r <= n yozish — keng tarqalgan xato. Har birining nozik farqi bor. Kod yozishdan oldin kichik misol ustida qo'lda kuzatib (dry run) ko'rish bu xatolarni oldindan topib beradi.

Traversal bilan barcha masalani hal qilishga urinish

Traversal eng sodda texnika, lekin har doim optimal emas. Siljuvchi oyna bilan O(n) da hal bo'ladigan masalani ichma-ich sikl bilan O(n²) da hal qilish katta hajmdagi ma'lumotda jiddiy muammo tug'diradi.

Katta-kichik harflarni e'tiborsiz qoldirish

'A' va 'a' aksariyat kodlashda turli belgilar. Masalada "katta-kichik harf ahamiyatsiz" deyilmagan bo'lsa, ularni bir xil deb hisoblash xatolikka olib keladi. Normalizatsiya kerak bo'lsa, uni boshidanoq bajarish va izchil qo'llash kerak.

Chastota jadvalini qayta ishlatishdan oldin tozalamaslik

Chastota jadvali bir testdan keyingi testda qayta ishlatilsa, avvalgi qoldiq qiymatlar noto'g'ri natijaga olib kelishi mumkin. Har safar yangi masalada yangi jadval yaratish yoki eski jadvalni nolga qaytarish kerak.

Qachon bu texnikalar yetarli emas?

Yuqorida ko'rilgan to'rtta texnika ko'plab string masalalarini hal qiladi. Lekin quyidagi holatlarda maxsus algoritmlar kerak bo'ladi:

• Juda uzun matnda patternni samarali qidirish — KMP yoki Boyer-Moore O(n + m).
• Ikkita string o'rtasidagi eng kichik farqni hisoblash — edit distance dinamik dasturlash yordamida.
• Ko'p patternni bir vaqtda qidirish — Aho-Corasick algoritmi.
• Eng uzun umumiy substring — dinamik dasturlash yoki suffix array.

Bu algoritmlar kuchli poydevorni talab qiladi. Asosiy to'rtta texnikani yaxshi o'zlashtirgan odam ularga ham tayyor bo'ladi.

---

Keyingi bo'limlarda shu texnikalarni aniq masalalarga qo'llab ko'ramiz: stringni teskari aylantirish, palindromni tekshirish, eng uzun umumiy prefiksni topish va takrorlanmagan belgilarning eng uzun qismini aniqlash.

---

📍 Toshkent, O'zbekiston
🗓️ 4-Avgust, 2026-yil
👤 Farrux Elomonov