Eng uzun umumiy prefiks
Bir nechta string berilganda, ularning barchasida boshidan umumiy bo'lgan eng uzun qismni topish kerak. Bu qism prefiks deb ataladi — stringning boshidan boshlanuvchi uzluksiz bo'lak.
Ko'rinib turibdiki, uchala string ham "fl" bilan boshlanadi. Uchinchi string "flight" "flo" bilan boshlanmaydi, shuning uchun "flo" emas, faqat "fl" umumiy.
Bu masala dizayn vositalarida, kompilyatorlarda, ma'lumotlar bazasi indekslarida va avtoto'ldirish (autocomplete) tizimlarida uchraydi. Foydalanuvchi "pro" deb boshlaganda tizim barcha mos so'zlarning umumiy qismini topib, saralashni optimallashtiradi.
Muammoning nozik tomoni
Darhol birinchi belgidan boshlab solishtirish boshlanishi kerak. Har bir belgi pozitsiyasida barcha stringlarda shu pozitsiyada bir xil belgi bormi yoki yo'qligi tekshiriladi. Birinchi farq topilishi bilanoq shu pozitsiyadagi qism umumiy prefiks hisoblanadi.
Ammo bu masalaning o'ziga xos cheklovi bor: umumiy prefiks istalgan ikkita string orasida emas, barcha stringlarda bir vaqtda umumiy bo'lishi kerak. Shuning uchun bitta string bilan boshqasini solishtirish yetarli emas.
Yondashuv 1: vertikal skanerlash
Eng tabiy yondashuv — barcha stringlarga bir vaqtda qarab, belgilarni ustun bo'yicha tekshirish. i pozitsiyasida barcha stringlarning i-chi belgisi bir xilmi? Agar ha — davom etiladi. Agar yo'q yoki biror string shu pozitsiyaga yetmagan bo'lsa — to'xtash vaqti.
strings = ["flower", "flow", "flight"]
i=0: 'f', 'f', 'f' → bir xil, davom
i=1: 'l', 'l', 'l' → bir xil, davom
i=2: 'o', 'o', 'i' → farq bor, TO'XTATISH
Natija: "fl"
FUNCTION vertikal_skanerlash(strings):
IF strings bo'sh:
RETURN ""
i = 0
WHILE i < strings[0].length:
belgi = strings[0][i]
j = 1
WHILE j < strings.length:
IF i >= strings[j].length OR strings[j][i] != belgi:
RETURN strings[0][0..i] // 0 dan i gacha (i kiritilmaydi)
j = j + 1
i = i + 1
RETURN strings[0][0..i]
Bu algoritm ikkita ichma-ich tsikl ishlatadi:
- tashqi tsikl
i— pozitsiyani belgilaydi; - ichki tsikl
j— shu pozitsiyadagi barcha stringlarni tekshiradi.
Birinchi string mos kelgan deb qabul qilinadi, qolganlar u bilan solishtiriladi.
Dry run: vertikal skanerlash
["flower", "flow", "flight"] ustida:
strings[0] = "flower"
strings[1] = "flow"
strings[2] = "flight"
i=0, belgi='f':
j=1: strings[1][0]='f' == 'f' ✓
j=2: strings[2][0]='f' == 'f' ✓
i=1, belgi='l':
j=1: strings[1][1]='l' == 'l' ✓
j=2: strings[2][1]='l' == 'l' ✓
i=2, belgi='o':
j=1: strings[1][2]='o' == 'o' ✓
j=2: strings[2][2]='i' != 'o' ✗
RETURN strings[0][0..2] = "fl"
Yondashuv 2: gorizontal skanerlash
Ikkinchi yondashuv — stringlarni birin-ketin ikkitadan solishtirish. Avval birinchi va ikkinchi string orasidagi umumiy prefiks topiladi. Keyin topilgan prefiks uchinchi string bilan solishtiriladi. Va hokazo — har bir qadamda joriy prefiks qisqarishi mumkin, lekin uzayib keta olmaydi.
FUNCTION gorizontal_skanerlash(strings):
IF strings bo'sh:
RETURN ""
prefiks = strings[0]
i = 1
WHILE i < strings.length:
WHILE strings[i] da prefiks yo'q (boshida emas):
prefiks = prefiksning oxirgi belgisini olib tashlash
IF prefiks bo'sh:
RETURN ""
i = i + 1
RETURN prefiks
Bu yondashuv quyidagicha ishlaydi:
strings = ["flower", "flow", "flight"]
Boshlang'ich prefiks: "flower"
i=1, strings[1]="flow":
"flow" da "flower" bormi? Yo'q
prefiks → "flowe"
"flow" da "flowe" bormi? Yo'q
prefiks → "flow"
"flow" da "flow" bormi? Ha ✓
i=2, strings[2]="flight":
"flight" da "flow" bormi? Yo'q
prefiks → "flo"
"flight" da "flo" bormi? Yo'q
prefiks → "fl"
"flight" da "fl" bormi? Ha ✓
Natija: "fl"
Ikkala yondashuvni solishtirish
Ikkala yondashuv ham to'g'ri natija beradi. Lekin ularning xatti-harakati ba'zi holatlarda farq qiladi.
Vertikal skanerlash — eng kichik stringga yetishi bilanoq to'xtashi mumkin. Agar birinchi belgidan farq chiqsa, faqat n ta solishtirish bajariladi (n — stringlar soni). Kalta stringlar ko'p bo'lsa qulay.
Gorizontal skanerlash — barcha stringlarni birin-ketin ko'rib chiqadi. Oxirgi string bilan solishtirish paytiga kelib prefiks ancha qisqargan bo'lishi mumkin. Lekin har bir qadamda string ustida boshidan skanerlash talab qilinishi mumkin — bu qo'shimcha ish.
Amalda ikkalasining vaqt murakkabligi bir xil: O(S) — barcha stringlardagi jami belgilar soni. Sababi quyidagicha: eng yomon holatda har bir belgi bir marta ko'riladi.
Chegara holatlari
Bo'sh massiv: Umumiy prefiks yo'q — bo'sh string qaytariladi.
Bitta string: U o'zining o'zi bilan umumiy prefiksga ega — o'zi qaytariladi.
Barcha stringlar bir xil: Umumiy prefiks — o'sha string o'zi.
Umumiy prefiks yo'q: Birinchi belgidanoq farq bor — bo'sh string qaytariladi.
Bitta string bo'sh string: Bo'sh string bilan hech narsaning umumiy prefiksi bo'lmasligi mumkin — bu ham bo'sh string qaytaradi.
Warning
Eng qisqa stringning uzunligidan oshib ketadigan pozitsiyani tekshirishga harakat qilmaslik kerak. Vertikal skanerlashda i >= strings[j].length shartini har doim belgi taqqoslashdan oldin tekshirish kerak — aks holda chegaradan tashqaridagi indeksga murojaat qilinadi.
Vaqt va xotira murakkabligi
| Yondashuv | Vaqt murakkabligi | Xotira murakkabligi |
|---|---|---|
| Vertikal skanerlash | O(S) | O(1) |
| Gorizontal skanerlash | O(S) | O(1) |
S — barcha stringlardagi jami belgilar soni. Har ikki yondashuv ham O(1) qo'shimcha xotira ishlatadi — faqat ko'rsatkichlar saqlanadi.
Eng yaxshi holat — birinchi belgidan farq chiqsa: O(n) (n — stringlar soni). Eng yomon holat — barcha stringlar bir xil bo'lsa: O(S).
Nega bu masala muhim?
Umumiy prefiks qidirish trie (prefix tree) ma'lumotlar tuzilmasining asosidagi g'oya. Avtoto'ldirish tizimlarida, lug'at qidiruvida va marshrutlash (routing) algoritmlarida prefiks bo'yicha guruhlashtirish keng qo'llanadi. Bu masalani yechishning har ikki yondashuvi ham trie bilan ishlashda foydali bo'ladigan fikrlash tarzini rivojlantiradi.