Dasturchi, frilanser, gik va introvert
Regular expression (yana regex, regexp) - qidirish patternini belgilab beruvchi belgilar ketma-ketligi. Odatda regex'lar matn ichida qidiruv algoritmlarida so'zlarni topish (find), topish va almashtirish (find & replace), hamda kiritilgan ma'lumotni tekshirish uchun ishlatiladi.
Matn ichida qidiruv uchun yana bir diqqatga molik algoritmlardan biri - Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning ishlash tartibini batafsil tushuntirishga harakat qilaman.
Avvalgi mavzuda o'tganimiz - Knuth-Morris-Pratt algoritmi yordamida biz matn ichida qidiruvni O(N + M) vaqt ichida bajara olamiz. Navbatdagi algoritm - Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq ishlaydi. O'rganishga ham osonroq ;)
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.
Matn ichida so'z/ibora qidiruv (substring search) algoritmlari bilan tanishib chiqishni boshlaymiz. Qo'yiladigan masala juda oddiy. N uzunlikdagi matn ichidan M uzunlikdagi iborani (pattern) topish kerak bo'lsin. Bunda matn juda katta hajmda, pattern esa juda kichik - bir-ikki so'zdan iborat.