Palindromni tekshirish
Palindrom — boshidan o'qilganda ham, oxiridan o'qilganda ham bir xil bo'ladigan ketma-ketlik. Tanish misollar: "aba", "level", "racecar", "noon". O'zbek tilidagi "ada" yoki "ata" so'zlari ham palindrom.
"racecar" → r-a-c-e-c-a-r → teskari ham "racecar" → palindrom
"salom" → s-a-l-o-m → teskari "molas" → palindrom emas
Bu masala o'z-o'zicha foydali, lekin uning asosiy ahamiyati boshqa joylarda ham namoyon bo'ladi. DNK ketma-ketliklarida palindromik bo'laklar biologik ma'noga ega. Kriptografiyada ma'lum tuzilmalar palindromik xossalarga tayanadi. Eng muhimi esa — bu masala ikki ko'rsatkich texnikasining klassik namunasidir va uni yechish orqali texnikani chuqur tushunish mumkin.
Birinchi g'oya: teskari qilib solishtirish
Eng tushunarli yondashuv — stringni teskari aylantirish va asl string bilan solishtirish:
FUNCTION palindrommi_tekshirish_sodda(s):
teskari = s ni teskari qilish
IF s == teskari:
RETURN rost
ELSE:
RETURN yolg'on
Bu yondashuv to'g'ri ishlaydi. Lekin u O(n) qo'shimcha xotira talab qiladi — teskari string uchun yangi joy ajratiladi.
Bundan ham muhimi: bu yondashuv aslida keraksiz ish bajaradi. Teskari aylantirish uchun barcha n belgini ko'rib chiqish kerak, keyin solishtirish uchun yana n belgini ko'rib chiqish kerak. Jami 2n qadam. Lekin palindromni aniqlash uchun aslida stringning faqat yarmini ko'rish yetarli.
Ikki ko'rsatkich: faqat yarmini ko'rish
Samaraliroq yondashuv — ikkita ko'rsatkich yordamida boshdan va oxirdan bir vaqtda yurish. Har qadamda ikkala ko'rsatkich ko'rsatgan belgilarni solishtirish kerak. Agar ular bir xil bo'lsa, ko'rsatkichlar markazga tomon yaqinlashadi. Agar farq chiqsa — string palindrom emas.
FUNCTION palindrommi(s):
l = 0
r = s.length - 1
WHILE l < r:
IF s[l] != s[r]:
RETURN yolg'on
l = l + 1
r = r - 1
RETURN rost
Bu yondashuv O(1) qo'shimcha xotira ishlatadi — faqat ikkita ko'rsatkich saqlanadi.
Dry run: bosqichma-bosqich kuzatish
"racecar" (7 belgi) ustida:
indeks: 0 1 2 3 4 5 6
[r] [a] [c] [e] [c] [a] [r]
^ ^
l=0 r=6
Qadam 1: s[0]='r' == s[6]='r' ✓
l=1, r=5
Qadam 2: s[1]='a' == s[5]='a' ✓
l=2, r=4
Qadam 3: s[2]='c' == s[4]='c' ✓
l=3, r=3
l < r sharti bajarilmaydi (3 < 3 yolg'on).
Tsikl to'xtaydi. RETURN rost.
"salom" (5 belgi) ustida:
Murakkablashtirilgan variant: belgilarni filtrlash
Real masalalarda palindromni tekshirish ko'pincha "bo'sh joy va tinish belgilarini e'tiborga olmasdan, katta-kichik harfni ahamiyatsiz deb hisoblagan holda tekshir" shaklida beriladi:
Kirish: "A man, a plan, a canal: Panama"
Javob: rost (faqat harflar va raqamlar: "amanaplanacanalpanama")
Bunday holda bir nechta qo'shimcha qadam kerak:
- Har bir belgini ko'rib chiqishdan oldin uni filtrlash — faqat harf yoki raqam bo'lsa tekshirishga kiritish.
- Katta harfni kichikka (yoki aksincha) keltirish.
FUNCTION palindrommi_filtrlab(s):
l = 0
r = s.length - 1
WHILE l < r:
WHILE l < r AND s[l] harf yoki raqam emas:
l = l + 1
WHILE l < r AND s[r] harf yoki raqam emas:
r = r - 1
IF kichik(s[l]) != kichik(s[r]):
RETURN yolg'on
l = l + 1
r = r - 1
RETURN rost
Bu yondashuvda l va r faqat "kerakli" belgiga to'g'ri kelganda solishtirish bajariladi. Boshqa belgilar o'tkazib yuboriladi.
Dry run: filtrlangan variant
"A man, a plan, a canal: Panama" ustida (qisqartirilgan):
l → 'A' (harf, qoladi), r → 'a' (harf, qoladi)
kichik('A') == kichik('a') → 'a' == 'a' ✓ l++, r--
l → ' ' (bo'sh joy, o'tkazib yubor) → l++
l → 'm' (harf, qoladi), r → 'm' (harf, qoladi)
kichik('m') == kichik('m') ✓ l++, r--
... va hokazo, oxirigacha ✓
RETURN rost
Chegara holatlari
Bo'sh string: l = 0, r = -1. 0 < -1 yolg'on. Tsikl boshlanmaydi. Bo'sh string palindrom hisoblanadi — bu kelishilgan ta'rif, masalaga qarab o'zgarishi mumkin.
Bitta belgi: l = 0, r = 0. 0 < 0 yolg'on. Bitta belgi har doim palindrom.
Ikkita bir xil belgi: "aa". Bir marta solishtirish, ular teng, tsikl to'xtaydi. Rost.
Ikkita turli belgi: "ab". Bir marta solishtirish, ular teng emas. Yolg'on.
Faqat bo'sh joy va tinish belgilaridan iborat: Filtrlovchi variantda l va r hech qachon kerakli belgiga yetmaydi. l < r sharti algoritm davomida bajarilmay qoladi. Natija rost — bu masalaga qarab kutilgan javob bo'lishi yoki bo'lmasligi mumkin. Masalani o'qishda bu holat ko'rsatilganmi deb tekshirish kerak.
Warning
"Palindrom" ta'rifi masalaga qarab o'zgarishi mumkin. Ba'zi masalalarda bo'sh string palindrom, ba'zilarida emas. Ba'zilarida katta-kichik harf ahamiyatli, ba'zilarida emas. Masalani o'qishda bu shartlarni aniq belgilash kerak.
Vaqt va xotira murakkabligi
| Yondashuv | Vaqt murakkabligi | Xotira murakkabligi |
|---|---|---|
| Teskari qilib solishtirish | O(n) | O(n) |
| Ikki ko'rsatkich | O(n) | O(1) |
| Ikki ko'rsatkich + filtrlash | O(n) | O(1) |
Ikkala asosiy yondashuv ham O(n) vaqtda ishlaydi. Farq xotirada: teskari aylantirish O(n) qo'shimcha joy talab qilsa, ikki ko'rsatkich O(1) bilan cheklanadi.
Vaqt murakkabligiga nisbatan: ikki ko'rsatkich yondashuvida ko'pi bilan n/2 ta solishtirish bajariladi — birinchi farq chiqishi bilanoq to'xtaydi. Shuning uchun amalda teskari aylantirish yondashuvidan tezroq ishlaydi, ammo O notatsiyasida ikkisi ham O(n).
Bu masalaning davomi
Palindromni tekshirish o'zi tugallanmaydi. Uning bir nechta kengaytmasi mavjud:
- Eng uzun palindromik substring — berilgan string ichidagi eng uzun palindromni topish (dinamik dasturlash yoki "markazdan kengayish" texnikasi).
- Ko'p miqdorda string ichidan palindromlarni hisoblash — har bir substring palindrommi degan savolga javob berish.
- Linked list palindrommi — bu holat pointer boshqaruvi va runner texnikasini birlashtiradi.
Ikki ko'rsatkich texnikasining bu masaladan olingan tushunchasi boshqa ko'plab muammolarda ham qo'l keladi.