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.

Matn içida qidiruv masalalari amaliyotda hujjatlar içidan kerakli sözni qidirişda, email kontent içidan şubhali sözni topib spam qilib belgilaşda, web-sahifadan ma'lumotni köçirişda (web-scraping), internet traffikni nazorat qilişda, va h.k. işlatiladi. Katta hajmdagi ma'lumotlar bilan işlaşda esa qidiruvning tez amalga oşişi muhim rol öynaydi.

Stringda kerakli sözni qidiriş uçun dasturlaş tillarida tayyor funksiyalar allaqaçon mavjud. Masalan, Javascriptda str.indexOf(pattern) funksiyasi qidirilayotgan sözni (pattern) topib, uning birinçi belgisi joylaşgan indeksni qaytaradi.

Biz xorijiy big-tech kompaniyalarga işga kiriş intervyusiga tayyorlaniş uçun, matn içida qidiruv algoritmlarini örganamiz.

Brute-force yondaşuvi

Odatiy usul albatta ikki siklda işlaydigan brute-force algoritmi böladi. Demak, bizda quyidagi matn bor bölsin: ABACADABRAC. Biz uning içidan ABRA sözini qidiramiz.

Birinçi sikl i = [0..N] gaça yoki ikkinçi siklda j = M bölgunça işlaydi. Bunda N - matnning uzunligi, undagi belgilar soni.

Ikkinçi sikl j = [i...M] gaça yoki str[i + j] != pattern[j] bölgunça işlaydi. Bunda M - pattern uzunligi.

Kod

Kodning işlaş vaqti - O(N * M). N * M, ya'ni worst case holati matnda qaytariluvçi belgilar köpligida böladi. Masalan, matn AAAAAAAAAB va pattern AAAAB bölsa, patternni topgunça har safar ikkinçi (içki) sikl j < M - 1 gaça işlaydi.

Katta matnlar bilan işlaş uçun brute-force yondaşuvi ma'qul yöl emas, u köp vaqt talab qiladi. Nazariy jihatdan pattern'ni linear vaqtda - O(N) da topiş ideal variant bölardi.

Keyingi maqolalarda matn içida qidiruvning samaraliroq algoritmlarini körib ötamiz.