Matn algoritmlari: normallash, palindrom, so'zlarni teskari, siqish va qism-satr qidirish

Qisqacha: Matn masalalarining ko'pi ikki qadamdan iborat. Avval normallash: matnni bir xil shaklga keltirish (kichik harf, apostrofning olti xil yozilishi — bitta, ketma-ket bo'shliqlar — bitta probel) — O(L). Keyin algoritm: palindrom — ikki ko'rsatkich, anagramma — hisoblagich, so'zlarni teskari — split + reverse + join, siqish — ketma-ket bir xil harflarni sanash, hammasi O(L). Qism-satr qidirishning oddiy usuli eng yomon holatda O(n · m); KMP mos kelgan qismni qayta solishtirmaydi — O(n + m). JavaScript'ning includes/indexOf ichida ham shunga o'xshash aqlli algoritmlar bor.

Bu darsda

• Matnni qidiruv va solishtirish uchun normallaysiz — o'zbekcha apostroflar bilan ham.
• Palindromni ikki ko'rsatkich bilan, so'zlarni teskari aylantirishni va matnni siqishni O(L) da yozasiz.
• Oddiy qism-satr qidiruvi qachon O(n · m) ga tushishini ko'rasiz va KMP g'oyasini tushuntira olasiz.
• vazifalar ilovasiga apostrof va harf farqsiz qidiruv qo'shasiz — topilgan bo'laklar <mark> bilan belgilanadi.

Oldin bilishingiz kerak: Hash map bilan hisoblash naqshlari, Ikki ko'rsatkich, Unicode va emoji: matn ichki tuzilishi, Matn ichida qidirish, Unicode regex: u va v flag.

1. Nega bu kerak?

Malika vazifalar ilovasidan foydalanadi — ekran o'qigich (NVDA) bilan. U ro'yxatda "o'quv" so'zi bor vazifani izlamoqchi. Ammo vazifani telefonda yozgan: telefon klaviaturasi o' harfini oʻ qilib qo'ygan. Kompyuterda u oddiy ' bilan yozadi. JavaScript uchun bu ikki xil satr:

console.log("Oʻquv rejasi".toLowerCase().includes("o'quv")); // false

Ko'zga bir xil ko'rinadi, lekin kompyuter uchun ʻ (U+02BB) va ' (U+0027) — boshqa-boshqa belgilar (Unicode va emoji). O'zbek matnida o' va g' kamida olti xil yoziladi. Katta-kichik harf, ortiqcha bo'shliqlar ham qo'shilsa — oddiy includes ko'p narsani "topmaydi".

Bugungi dars ikki qismdan. Birinchisi — matn bilan ishlashning klassik algoritmlari: intervyularning eng ko'p uchraydigan savollari. Ikkinchisi — ularning hammasi tayanadigan qadam, normallash, va vazifalar dagi haqiqiy qidiruv. Satrni teskari aylantirish kabi masalalarga String asoslari darsida va'da bergan edik — shu yerda.

2. Normallash — har matn algoritmining birinchi qadami

2.1 Bir xil shaklga keltirish

Normallash (normalization) — matnni solishtirish uchun yagona shaklga keltirish. Qaysi farqlar "muhim emas" — buni vazifa belgilaydi. Qidiruv uchun odatda uchtasi:

1. Harf katta-kichikligi: O'QUV = o'quv → toLowerCase().
2. Apostroflar: ', ‘, ’, ʻ, ʼ, ` → bitta '.
3. Bo'shliqlar: bir nechta probel, tab, yangi qator → bitta probel; boshi va oxiri kesiladi.

const APOSTROPHES = /['‘’ʻʼ`]/g;

function normalize(text) {
  return text
    .toLowerCase()
    .replace(APOSTROPHES, "'") // olti xil apostrof — bitta
    .replace(/\s+/g, " ") // bir nechta bo'shliq — bitta probel
    .trim();
}

console.log(normalize("  Oʻquv   REJASI ")); // o'quv rejasi
console.log(normalize("O‘QUV") === normalize("o'quv")); // true

Har zanjir qadami matnni bir marta aylanadi: L belgili matn uchun 3–4 o'tish, jami O(L). \s+ — bir yoki ko'p bo'shliq belgisi (Belgi klasslari).

2.2 Qidiruvda ikkala tomon ham normallanadi

Qoida: so'rov ham, matn ham bir xil funksiyadan o'tadi. Faqat bittasini normallasangiz, O'QUV so'rovi o'quv matnini topmaydi. Ko'p vazifali ro'yxatda so'rov bir marta normallanadi, har vazifa matni — bir marta: n ta vazifa, har biri L belgi — O(n · L).

Diqqat: Normallangan matnni foydalanuvchiga ko'rsatmang. U faqat solishtirish uchun. Ekranda Malika o'z yozganini ko'rishi kerak — Oʻquv, katta harf bilan. Topilgan bo'lakni belgilash uchun esa normal matndagi o'rinni asl matndagi o'ringa qaytarish kerak bo'ladi — buni "Vazifalar qadami" da ko'ramiz.

3. Palindrom

Palindrom — oldidan ham, orqasidan ham bir xil o'qiladigan so'z yoki ibora: kiyik, non, tot. Iboralarda tinish belgilari va bo'shliqlar hisobga olinmaydi.

Sodda yechim: normallab, teskari nusxa yasab, solishtirish. Bu O(L) vaqt va O(L) qo'shimcha xotira. Ikki ko'rsatkich bilan nusxasiz ham bo'ladi. Chetlardan markazga yurib, harflarni juftlab solishtiramiz va harf bo'lmaganlarni o'tkazib yuboramiz. \p{L} — har qanday tildagi harf (Unicode regex):

Har belgi ko'pi bilan bir marta ko'rildi — O(L). Biror juft farq qilsa — darhol false, oxirigacha borish shart emas.

Tekshirib ko'ring: isPalindrome("Non bor") nima qaytaradi va nechta harf juftini solishtiradi? isPalindrome("Non, non") chi?

4. So'zlarni teskari aylantirish

"osh va manti" → "manti va osh". Satr o'zgarmas (String asoslari), shuning uchun so'zlar massiviga bo'lamiz, massivni teskari qilamiz va qayta yig'amiz:

function reverseWords(text) {
  return text.trim().split(/\s+/).reverse().join(" ");
}

console.log(reverseWords("  osh   va manti ")); // manti va osh

split(/\s+/) — bir yoki ko'p bo'shliq bo'yicha bo'ladi, shuning uchun ortiqcha probellar bo'sh so'z bermaydi. Uch qadam, har biri O(L) — jami O(L) vaqt va xotira.

Harflarni teskari aylantirishda esa tuzoq bor. split("") satrni UTF-16 birliklarga bo'ladi va emoji ikkiga bo'linib, buziladi. [...text] esa kod nuqtalari bo'yicha bo'ladi:

const label = "🍞non";
console.log("🍞".length, [..."🍞"].length); // 2 1
console.log([...label].reverse().join("")); // non🍞
const broken = label.split("").reverse().join("");
console.log(broken === "non🍞"); // false

🍞 — ikki UTF-16 birligi. split("") uni ikki yarimga ajratdi va teskari tartibda yopishtirdi — natija buzilgan belgi. Matnni belgilarga bo'lishda doim [...text] yoki for...of (Unicode va emoji). Bayroqlar va oilaviy emojilar kabi bir necha kod nuqtasidan iborat belgilar uchun hatto bu ham yetmaydi — Intl.Segmenter kerak (Intl.Segmenter).

5. Matnni siqish

Kassa printeri xotirasi kichik. Chekdagi chiziq "------" kabi takroriy belgilarni siqib saqlash kerak: "aaabccccd" → "a3b1c4d1". Bu usul RLE (run-length encoding) — "ketma-ketlik uzunligi bo'yicha kodlash" deb ataladi. Siqilgan matn uzunroq chiqsa — aslini qaytaramiz:

function compress(text) {
  let result = "";
  let i = 0;
  while (i < text.length) {
    let j = i;
    while (j < text.length && text[j] === text[i]) j++; // bir xillar
    result += text[i] + (j - i);
    i = j; // keyingi guruhga sakraymiz
  }
  return result.length < text.length ? result : text;
}

console.log(compress("aaabccccd")); // a3b1c4d1
console.log(compress("osh")); // osh

Ichma-ich ikki sikl, lekin O(L²) emas: j faqat oldinga yuradi va i ga sakraydi. Har belgi bir marta ko'riladi — O(L). Bu — ikki ko'rsatkich darsidagi "o'qish" ko'rsatkichining yana bir ko'rinishi. result += ham muammo emas: V8 da satr birlashtirish siklda ham chiziqli (JS amallarining narxi).

6. Qism-satr qidirish

6.1 Oddiy usul

text.includes(pattern) ichida nima bo'ladi? Eng oddiy javob: naqshni matnning har joyiga qo'yib, harfma-harf solishtirish. Mos kelmasa — bir qadam o'ngga surib, qaytadan boshidan:

Oddiy holatda birinchi harfdayoq farq chiqadi va ish tez. Lekin eng yomon holatni o'ylang: matn — 200 000 ta a, naqsh — aaa…ab. Har joyda naqshning deyarli hammasi mos keladi, faqat oxirgi b da farq chiqadi. Har joyda m ta solishtirish, n ta joy — O(n · m).

6.2 KMP g'oyasi

Oddiy usulning isrofi: mos kelgan qismni unutadi. ababc naqshi ababa… matnida 4 ta harf mos keldi, 5-chisida farq chiqdi. Biz abab ni allaqachon o'qidik. Uning oxiridagi ab naqshning boshi bilan bir xil! Demak, naqshni shunday surish mumkinki, ab mos kelgan holda qolsin — va 3-harfdan davom etish kerak, matnda orqaga qaytmasdan.

KMP algoritmi (Knuth–Morris–Pratt, 1977) shu g'oyani oldindan hisoblangan jadval bilan qiladi. lps[i] — naqshning birinchi i + 1 harfida "ham boshi, ham oxiri bo'lgan eng uzun qism" uzunligi (o'zi bundan mustasno). Nomi — inglizcha "longest prefix which is also suffix" qisqartmasi. Jadvalni qatorma-qator o'qing — abab da boshi ham, oxiri ham ab:

function buildLps(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0; // hozirgi "boshi = oxiri" uzunligi
  for (let i = 1; i < pattern.length; ) {
    if (pattern[i] === pattern[len]) lps[i++] = ++len;
    else if (len > 0) len = lps[len - 1]; // qisqaroq variantga
    else lps[i++] = 0;
  }
  return lps;
}

function kmpSearch(text, pattern) {
  if (pattern === "") return 0;
  const lps = buildLps(pattern);
  let j = 0; // naqshda nechta harf mos kelgan
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}

console.log(buildLps("ababc")); // [ 0, 0, 1, 2, 0 ]
console.log(kmpSearch("abababc", "ababc")); // 2
console.log(kmpSearch("manti, mastava", "mast")); // 7

Asosiy xususiyat: i (matndagi joy) hech qachon orqaga qaytmaydi. Farq chiqsa, faqat j (naqshdagi joy) jadval bo'yicha kichrayadi. j jami ko'pi bilan n marta oshadi, demak ko'pi bilan n marta kamayadi ham — amortizatsiya. Jadval — O(m), qidiruv — O(n): jami O(n + m).

KMP ni yod olish shart emas — intervyularda u kam so'raladi. Muhimi g'oya: mos kelgan qism haqidagi ma'lumotni tashlab yubormaslik. Bu g'oya Trie va boshqa matn tuzilmalarida ham uchraydi.

6.3 O'lchov: eng yomon holat

Matn — 200 000 ta a, naqsh — (m − 1) ta a va oxirida b (topilmaydi). olcha, 7 o'lchov medianasi:

Oddiy usul: m ikki baravar — vaqt ikki baravar (n o'zgarmas, O(n · m)). KMP va indexOf — m ga bog'liq emas. Qizig'i, indexOf hatto KMP dan tez. Sababi: V8 naqsh uzunligiga qarab algoritm tanlaydi — qisqa naqsh uchun oddiy qidiruv, uzunroq uchun Boyer–Moore oilasi (naqshni oxiridan solishtirib, katta sakrashlar qiladi). Xulosa: amalda includes/indexOf ni ishlating. O'zingiz yozadigan joy — "mos kelgan qismni eslab qolish" kerak bo'lgan maxsus masalalar.

7. Chegaraviy holatlar

• Bo'sh satr. "osh".includes("") — true: bo'sh naqsh har joyda "bor". kmpSearch da shu sababli alohida qator. Bo'sh qidiruv so'rovi esa ilovada "hammasini ko'rsat" degani.
• Faqat bo'shliq. normalize(" ") → "". So'rov bo'sh deb hisoblanadi.
• Emoji va murakkab belgilar. [...text] yoki for...of; split("") emas.
• Kichiklashganda uzayadigan harf. "İ".toLowerCase() — ikki belgi (i + nuqta). Normal matndagi indeks asl matndagi indeksga teng emas — belgilashda siljish chiqadi. vazifalar dagi qidiruv buni hisobga oladi — "Vazifalar qadami" dagi moslar ga qarang.
• Juda uzun matn. Normallash har qidiruvda takrorlanmasin — iloji bo'lsa, normal shaklni bir marta hisoblab saqlang.

8. Ko'p uchraydigan xatolar

8.1 Faqat bir tomonni normallash

text.toLowerCase().includes(query) — so'rov katta harf bilan bo'lsa topilmaydi. Tuzatish: bitta normalize funksiyasi, ikkala tomonga.

8.2 Normallangan matnni ko'rsatish

Ekranda o'quv rejasi — foydalanuvchi yozgan Oʻquv rejasi emas. Tuzatish: normal shakl faqat solishtirish uchun.

8.3 split("") bilan harflarga bo'lish

Emoji buziladi. Tuzatish: [...text].

8.4 Siklda slice bilan qism-satrlarni solishtirish

text.slice(i, i + m) === pattern — har joyda yangi satr yasaydi, O(n · m) vaqt va keraksiz xotira. Tuzatish: indexOf yoki startsWith(pattern, i).

9. Mashqlar

1-mashq (oson): Normallang

normalize nima qaytaradi? (a) "\tG‘ISHT zavodi\n" (b) " " (c) "Ozbekiston"` (orqa tirnoq bilan).

2-mashq (o'rta): Anagramma — normallash bilan

O'tgan darsdagi isAnagram ni yaxshilang: isAnagramText(a, b) katta-kichik harf va bo'shliqlarni hisobga olmasin, faqat harflarni solishtirsin. "Bahor" va "ROBAH" → true, "osh choy" va "choyosh" → true, "osh" va "oshh" → false.

Ishora: avval har matndan faqat harflarni olib, kichik qiling: [...text.toLowerCase()].filter((ch) => /\p{L}/u.test(ch)). Keyin hisoblagich.

const lettersOf = (text) =>
  [...text.toLowerCase()].filter((ch) => /\p{L}/u.test(ch));

function isAnagramText(a, b) {
  const x = lettersOf(a);
  const y = lettersOf(b);
  if (x.length !== y.length) return false;
  const count = new Map();
  for (const ch of x) count.set(ch, (count.get(ch) ?? 0) + 1);
  for (const ch of y) {
    const left = (count.get(ch) ?? 0) - 1;
    if (left < 0) return false;
    count.set(ch, left);
  }
  return true;
}

console.log(isAnagramText("Bahor", "ROBAH")); // true
console.log(isAnagramText("osh choy", "choyosh")); // true
console.log(isAnagramText("osh", "oshh")); // false

3-mashq (qiyin): Matn funksiyalari testlari

kurs/mashqlar/14/11-matn/matn.test.mjs faylida darsdagi normalize, isPalindrome, compress va kmpSearch ni yozing. Testlar (node:test):

1. normalize — olti xil apostrof bitta natija beradi; bo'shliqlar.
2. isPalindrome — "Kiyik, kiyik!", "non", bo'sh satr (true), "osh" (false).
3. compress — "aaabccccd", siqish foyda bermaydigan "osh", bo'sh satr.
4. kmpSearch 300 ta urug'li tasodifiy matnda (faqat a va b, uzunligi 0–30; naqsh 1–5) indexOf bilan bir xil.

// kurs/mashqlar/14/11-matn/matn.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const APOSTROPHES = /['‘’ʻʼ`]/g;
const normalize = (text) =>
  text.toLowerCase().replace(APOSTROPHES, "'")
    .replace(/\s+/g, " ").trim();

const isLetter = (ch) => /\p{L}/u.test(ch);
function isPalindrome(text) {
  const s = text.toLowerCase();
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (!isLetter(s[left])) left++;
    else if (!isLetter(s[right])) right--;
    else if (s[left++] !== s[right--]) return false;
  }
  return true;
}

function compress(text) {
  let result = "";
  for (let i = 0, j = 0; i < text.length; i = j) {
    while (j < text.length && text[j] === text[i]) j++;
    result += text[i] + (j - i);
  }
  return result.length < text.length ? result : text;
}

function kmpSearch(text, pattern) {
  if (pattern === "") return 0;
  const lps = new Array(pattern.length).fill(0);
  for (let i = 1, len = 0; i < pattern.length; ) {
    if (pattern[i] === pattern[len]) lps[i++] = ++len;
    else if (len > 0) len = lps[len - 1];
    else lps[i++] = 0;
  }
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}

test("normalize — apostroflar va bo'shliqlar", () => {
  const forms = ["o'q", "o‘q", "o’q", "oʻq", "oʼq", "o`q"];
  assert.deepEqual(new Set(forms.map(normalize)), new Set(["o'q"]));
  assert.equal(normalize("  Non \t olish\n"), "non olish");
});

test("isPalindrome", () => {
  assert.equal(isPalindrome("Kiyik, kiyik!"), true);
  assert.equal(isPalindrome("non"), true);
  assert.equal(isPalindrome(""), true);
  assert.equal(isPalindrome("osh"), false);
});

test("compress", () => {
  assert.equal(compress("aaabccccd"), "a3b1c4d1");
  assert.equal(compress("osh"), "osh");
  assert.equal(compress(""), "");
});

test("kmpSearch — indexOf bilan bir xil", () => {
  let seed = 2026;
  const random = () => (seed = (seed * 16807) % 2147483647);
  const word = (n) =>
    Array.from({ length: n }, () => "ab"[random() % 2]).join("");
  for (let t = 0; t < 300; t++) {
    const text = word(random() % 31);
    const pattern = word(1 + (random() % 5));
    assert.equal(kmpSearch(text, pattern), text.indexOf(pattern));
  }
});

✔ normalize — apostroflar va bo'shliqlar (1.3873ms)
✔ isPalindrome (0.4162ms)
✔ compress (0.1454ms)
✔ kmpSearch — indexOf bilan bir xil (2.3379ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 85.8258

4-mashq: Vazifalar qadami — qidiruv

vazifalar ga 14-qismning birinchi qadami: ro'yxat ustida qidiruv maydoni. 13-qismda va'da bergan edik: "qidiruv 14-qismda". Talablar darsdagidek: apostrof va katta-kichik harf farqsiz, ortiqcha bo'shliqlar hisobga olinmaydi, topilgan bo'laklar ekranda <mark> bilan belgilanadi, natija soni ekran o'qigichga aytiladi. vazifalar kanoni o'zbekcha nomlar bilan yozilgan: normalize bu yerda normalla.

1. Branch:

git switch -c feature/qidiruv

2. Yangi fayl assets/js/qidiruv.js (// @ts-check, jsconfig.json ning include ro'yxatiga qo'shiladi). Darsdagi normalize dan farqi — u bir o'tishda, kod nuqtalari bo'yicha ishlaydi va kerak bo'lsa har normal belgining asl matndagi o'rnini eslab qoladi. Asosiy qismi (JSDoc izohlari qisqartirilgan, to'liq fayl — kanon repoda):

// @ts-check
// qidiruv.js — vazifalar ichida matn qidirish: normallash va moslar

// O'zbek matnida o' va g' bir necha xil yoziladi: ' (klaviatura),
// ‘ va ’ (U+2018, U+2019), ʻ (U+02BB, rasmiy), ʼ (U+02BC),
// ba'zan `. Qidiruvda hammasi bitta belgi: "o'quv" so'rovi
// "oʻquv" ni ham topadi
const APOSTROFLAR = new Set(["'", "‘", "’", "ʻ", "ʼ", "`"]);
const BOSHLIQ = /\s/u;

// normalShakl(matn, joylarKerak) — bitta o'tish: O(L)
// for...of — kod nuqtalari bo'yicha: emoji ikkiga bo'linmaydi;
// "İ" kichiklashganda ikki belgi — ikkalasi o'sha asl belgiga

export function normalla(matn) {
  return normalShakl(matn, false).toza;
}

export function qidir(vazifalar, sorov) {
  const toza = normalla(sorov);
  if (toza === "") {
    return [...vazifalar];
  }
  return vazifalar.filter((v) => normalla(v.matn).includes(toza));
}

export function moslar(matn, sorov) {
  const izlanadi = normalla(sorov);
  if (izlanadi === "") {
    return [];
  }
  const { toza, joylar } = normalShakl(matn, true);
  const natija = [];
  let joy = toza.indexOf(izlanadi);
  while (joy !== -1) {
    const oxiri = joy + izlanadi.length;
    natija.push([joylar[joy][0], joylar[oxiri - 1][1]]);
    joy = toza.indexOf(izlanadi, oxiri);
  }
  return natija;
}

Uch eksport, uch vazifa. normalla — darsdagi normalize ning o'zi. qidir so'rovni bir marta normallaydi, har vazifa matnini ham bir marta: O(n · (L + m)). Tartib saqlanadi, bo'sh so'rov — hamma vazifalar (nusxa). moslar — asl matndagi [boshi, oxiri) juftliklari: normal matnda indexOf bilan qidiradi, joylar jadvali orqali asl o'ringa qaytaradi. Mosliklar bir-birini qoplamaydi: keyingi qidiruv oxiri dan boshlanadi.

3. holat.js — holat.qidiruv = "" (URL'ga yozilmaydi: har harfda brauzer tarixiga yozuv tushardi) va ko'rinadigan vazifalar — avval filtr, keyin qidiruv:

// Filtr, keyin qidiruv: qidir tartibni saqlaydi
export function korinadiganlar() {
  return qidir(
    holat.vazifalar.korinadiganlar(holat.filtr),
    holat.qidiruv,
  );
}

vazifaQosh ga bitta qoida: yangi vazifa qidiruvga mos kelmasa, qidiruv tozalanadi — qo'shilgan vazifa ko'rinsin (filtr "bajarilgan" → "hammasi" qoidasi kabi).

4. render.js — topilgan bo'laklarni belgilash. innerHTML yo'q: matn tugunlari va <mark> elementlari (XSS va DOM xavfsizligi qoidasi):

function belgilanganMatn(matn) {
  const qismlar = [];
  let joy = 0;
  for (const [boshi, oxiri] of moslar(matn, holat.qidiruv)) {
    qismlar.push(matn.slice(joy, boshi));
    const belgi = document.createElement("mark");
    belgi.textContent = matn.slice(boshi, oxiri);
    qismlar.push(belgi);
    joy = oxiri;
  }
  qismlar.push(matn.slice(joy));
  return qismlar.filter((qism) => qism !== "");
}

Belgilash asl matnda: Malika Oʻquv ni ko'radi, o'quv ni emas. qidiruvniYoz() — #qidiruv-natija (role="status") ga "N ta topildi"; hech narsa topilmasa ro'yxat o'rnida "«…» bo'yicha vazifa topilmadi." role="status" — ekran o'qigich natija sonini o'zi aytadi.

5. index.html — HTML'ning <search> elementi ichida maydon va natija (assets/js/qidiruv.js uchun modulepreload ham qo'shiladi):

<search>
  <label for="qidiruv">Qidiruv</label>
  <input type="search" id="qidiruv" maxlength="100"
         autocomplete="off">
  <p id="qidiruv-natija" role="status"></p>
</search>

CSS: #qidiruv va mark uchun --rang-belgi (yorug' mavzuda #ffe08a, qorong'ida #5c4a00) — matn bilan kontrast 11:1 va 7:1. sw.js: VERSIYA — v4-4, QOBIQ ga qidiruv.js (oflayn ham ishlasin).

6. asosiy.js — debounce yo'q, va bu o'lchab qilingan qaror. 13-qismda qidiruvga debounce qo'yishni rejalagan edik. O'lchov boshqacha ko'rsatdi: qidiruv xotiradagi ro'yxatda, tarmoq va localStorage ga tegmaydi. qidir ning o'zi 1 000 vazifada ≈ 2,2 ms. Hodisadan qayta chizilguncha (Chrome 154) — 100 vazifada 5–7 ms, 1 000 da 48–60 ms. Vaqtning ko'pi — qayta chizish, qidiruv emas. Debounce chizishni arzonlashtirmaydi, faqat javobni kechiktiradi. 1 000 vazifagacha har harf INP "yaxshi" chegarasida (200 ms dan kam):

// Har harfda darhol, kechiktirishsiz (debounce yo'q): qidiruv
// xotiradagi ro'yxatda, tarmoq va localStorage'ga tegmaydi.
// O'lchandi: 1 000 vazifada qidirish ~2 ms, qayta chizish bilan
// ~50 ms — INP "yaxshi" chegarasi (200 ms) ichida; vaqtning
// ko'pi — chizish
function qidiruvniYangila() {
  holat.qidiruv = qidiruvMaydoni.value;
  holat.tahrirId = null;
  render();
}

input hodisasi Esc va maydondagi × tugmasida ham keladi (type="search"), shuning uchun alohida tinglovchi kerak emas. Import qilinganda — holat.qidiruv = "".

7. Testlar. tekshiruv/qidiruv.test.js — 15 ta test: normallash (3 — olti xil apostrof ham), qidir (4), moslar (5 — "İ", emoji, ko'p bo'shliq, qoplamaslik), holat bilan (3). Natija — 105/105; lint, format:check, tip — toza. Bittasi — chegaraviy holatlar bo'limidagi ikki tuzoq haqida:

test(
  "kichiklashganda cho'ziladigan harf va emoji siljitmaydi",
  () => {
    // "İ".toLowerCase() — ikki belgi; 🍞 — ikki UTF-16 birligi
    assert.deepEqual(moslar("İz", "z"), [[1, 2]]);
    assert.deepEqual(moslar("🍞 non", "NON"), [[3, 6]]);
  },
);

8. Brauzerda tekshirish — kanon tekshiruvining qidiruv qismi (9 ta vazifa JSON importi bilan; jami 133/133):

✅ qidiruv: o'quv — apostrof va harf farqsiz: [2,4,8,9]
✅ qidiruv: belgilangan bo'laklar (asl yozilishi): ["Oʻquv","o'quv","O‘QUV","o'quv","o'quv"]
✅ qidiruv: natija soni (role=status): ["4 ta topildi","status"]
✅ qidiruv: bo'shliqlar va katta harf: [[1],["Non olish"]]
✅ qidiruv: topilmadi — bosh xabar: [0,false,"«zzz» bo'yicha vazifa topilmadi.","0 ta topildi"]
✅ qidiruv: Esc tozaladi — hammasi qaytdi: ["",9,[]]
✅ qidiruv: mos kelmasa — tozalandi, yangi vazifa ko'rinadi: ["",true,""]
✅ qidiruv: so'rov HTML bo'lmaydi: [0,"«<b>» bo'yicha vazifa topilmadi."]

Ikkinchi qatorga qarang: belgilangan bo'laklar asl yozilishida — Oʻquv, O‘QUV. Oxirgisi — xavfsizlik: <b> so'rovi HTML sifatida emas, matn sifatida chiqdi.

9. Commit va PR. Xabar sarlavha va tanaga bo'lingan (sarlavha — 62 belgi, ≤ 72):

git add assets/js/qidiruv.js assets/js/holat.js assets/js/render.js \
  assets/js/asosiy.js index.html assets/css/vazifalar.css sw.js \
  jsconfig.json tekshiruv/qidiruv.test.js
git commit \
  -m "feat: qidiruv — apostrof va harf farqsiz, moslik belgilanadi" \
  -m "normalla O(L) bir o'tishda; debounce yo'q — o'lchandi"
git push -u origin feature/qidiruv
gh pr create --fill
gh pr merge --merge

Diff: 9 fayl, +313 −8. Murakkablik: normalla — O(L), qidir — O(n · (L + m)), moslar — faqat ekrandagi qatorlar uchun, O(L).

10. Real ishda

• Qidiruv maydonlari. Internet do'konlar, Telegram, kontaktlar — hammasida normallash bor: harf, diakritik belgilar (é → e), o'zbekcha apostroflar, ba'zan lotin/kirill. Katta tizimlar buni oldindan, "indeks" yasashda qiladi (Elasticsearch kabi qidiruv dvigatellari, keyingi qismlarda).
• Ma'lumotni tozalash. Ism, manzil, telefonni normallab solishtirish — takror mijozlarni topish (Hash map naqshlari).
• Matn tahrirlovchilar. VS Code'dagi Ctrl+F, grep — qism-satr qidirishning tezkor algoritmlari.
• Intervyu. "Valid Palindrome", "Reverse Words in a String", "String Compression", "Find the Index of the First Occurrence in a String" (LeetCode) — bugungi to'rt masala. KMP odatda "qo'shimcha savol" sifatida so'raladi.

Xulosa

• Matn algoritmlari ikki qadam: avval normallash (O(L)), keyin algoritm. So'rov ham, matn ham bir xil normallanadi; normal shakl ekranda ko'rsatilmaydi.
• Palindrom — ikki ko'rsatkich, O(L) va nusxasiz; so'zlarni teskari — split(/\s+/) + reverse + join; harflarga bo'lishda [...text].
• Siqish (RLE) — ichma-ich ikki sikl, lekin O(L): ichki ko'rsatkich faqat oldinga.
• Oddiy qism-satr qidiruvi eng yomon holatda O(n · m): 200 000 belgida 400 belgili naqsh — ≈ 377 ms. KMP — O(n + m), ≈ 2,4 ms; indexOf — ≈ 1 ms.
• vazifalar qidiruvi: normalla + includes, belgilash asl matnda, debounce yo'q — o'lchov shuni ko'rsatdi.

Keyingi dars: Matritsa bilan ishlash — zal xaritasi kabi 2D massivlarni qatorma-qator, spiral va to'rt yo'nalishda aylanish, 90° ga burish va transpozitsiya.

Manbalar

• Donald Knuth, James Morris, Vaughan Pratt, "Fast Pattern Matching in Strings", SIAM Journal on Computing, 1977 — KMP
• V8 manba kodi: src/strings/string-search.h — naqsh uzunligiga qarab qidiruv algoritmini tanlash (Boyer–Moore–Horspool, Boyer–Moore) — github.com/v8/v8
• Unicode Consortium: U+02BB MODIFIER LETTER TURNED COMMA — o'zbek lotin alifbosida o' va g' uchun — unicode.org
• MDN: String.prototype.normalize(), <search> elementi, <mark> elementi — developer.mozilla.org