{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Wyszukiwanie wzorca w tekście\n",
    "\n",
    "*Wersja notatnika: 2026-10-16 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "Ostatni temat z sylabusa. Ile razy w „Panu Tadeuszu” pada „Tadeusz”? Napiszesz wyszukiwanie naiwne, zobaczysz,\n",
    "jak algorytm Horspoola przeskakuje fragmenty tekstu, sprawdzisz, czego używa sam Python, i poznasz wyrażenia\n",
    "regularne — razem z pułapką, przez którą w 2019 r. strony obsługiwane przez Cloudflare przez ok. 27 minut\n",
    "zwracały błędy.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. W zadaniach zamień `pass` i `TODO` na swój kod i uruchom komórkę **Sprawdź**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Tekst: cały „Pan Tadeusz”\n",
    "2. Wbudowane: `in`, `find`, `count`\n",
    "3. Algorytm naiwny: okno przesuwane o jeden znak\n",
    "4. Najgorszy przypadek: O(n · m)\n",
    "5. Horspool: przeskocz, kiedy możesz\n",
    "6. Czego używa Python: `str.find` i Two-Way\n",
    "7. Wyrażenia regularne: wzorzec opisany regułą\n",
    "8. Pułapka: katastrofalne nawracanie\n",
    "9. Zadania 11.0–11.3 i zadanie 11.4 dla chętnych"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Tekst: cały „Pan Tadeusz”\n",
    "\n",
    "Tekst pobierzemy z Wolnych Lektur (utwór w domenie publicznej). Jeśli nie ma internetu, komórka użyje samej\n",
    "inwokacji wpisanej w kod."
   ]
  },
  {
   "cell_type": "code",
   "id": "k03",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import os\n",
    "import urllib.request\n",
    "\n",
    "URL = \"https://wolnelektury.pl/media/book/txt/pan-tadeusz.txt\"\n",
    "PLIK = \"pan-tadeusz.txt\"\n",
    "\n",
    "if not os.path.exists(PLIK):\n",
    "    try:\n",
    "        urllib.request.urlretrieve(URL, PLIK)\n",
    "    except OSError as e:\n",
    "        print(\"Brak internetu — używam samej inwokacji:\", e)\n",
    "\n",
    "if os.path.exists(PLIK):\n",
    "    with open(PLIK, encoding=\"utf-8\") as f:\n",
    "        tekst = f.read()\n",
    "else:\n",
    "    tekst = \"\"\"Litwo! Ojczyzno moja! ty jesteś jak zdrowie;\n",
    "Ile cię trzeba cenić, ten tylko się dowie,\n",
    "Kto cię stracił. Dziś piękność twą w całej ozdobie\n",
    "Widzę i opisuję, bo tęsknię po tobie.\"\"\"\n",
    "\n",
    "print(\"znaków:\", len(tekst))\n",
    "print(tekst[tekst.find(\"Litwo\"):tekst.find(\"Litwo\") + 44])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k04",
   "metadata": {},
   "source": [
    "## 2) Wbudowane: `in`, `find`, `count`\n",
    "\n",
    "Python ma gotowe narzędzia: `wzorzec in tekst` (czy jest), `tekst.find(wzorzec)` (indeks pierwszego wystąpienia\n",
    "albo `-1`) i `tekst.count(wzorzec)` (ile razy, bez nakładania). Wielkość liter ma znaczenie, a szukany jest\n",
    "**fragment napisu**, nie słowo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k05",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** `tekst.count(\"Tadeusz\")` daje 184. Ile razy pada samo słowo „Tadeusz”, bez końcówek?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> 107. `count` szuka fragmentu napisu, więc liczy też „Tadeusza” (54 razy), „Tadeuszu”, „Tadeuszku” i inne formy. Całe słowa policzysz wyrażeniem regularnym w części 7.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k06",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "print(\"Tadeusz\" in tekst, tekst.find(\"Tadeusz\"), tekst.find(\"Napoleon III\"))\n",
    "print(\"Tadeusz:\", tekst.count(\"Tadeusz\"), \"| Zosia:\", tekst.count(\"Zosia\"),\n",
    "      \"| Telimena:\", tekst.count(\"Telimena\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k07",
   "metadata": {},
   "source": [
    "## 3) Algorytm naiwny: okno przesuwane o jeden znak\n",
    "\n",
    "Przykładasz wzorzec do tekstu w pozycji 0 i porównujesz znak po znaku. Pierwsza różnica — przesuwasz okno o **jeden**\n",
    "znak i zaczynasz od nowa. Liczymy porównania, żeby mieć z czym porównać inne algorytmy."
   ]
  },
  {
   "cell_type": "code",
   "id": "k08",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def naiwne(tekst, wzorzec):\n",
    "    n, m = len(tekst), len(wzorzec)\n",
    "    wynik, porownania = [], 0\n",
    "    for i in range(n - m + 1):\n",
    "        j = 0\n",
    "        while j < m:\n",
    "            porownania += 1\n",
    "            if tekst[i + j] != wzorzec[j]:\n",
    "                break\n",
    "            j += 1\n",
    "        if j == m:\n",
    "            wynik.append(i)\n",
    "    return wynik, porownania\n",
    "\n",
    "start = time.perf_counter()\n",
    "pozycje, por_naiwne = naiwne(tekst, \"Tadeusz\")\n",
    "t_naiwne = time.perf_counter() - start\n",
    "print(\"wystąpień:\", len(pozycje), \"| porównań:\", por_naiwne)\n",
    "print(f\"czas: {t_naiwne * 1000:.1f} ms | znaków tekstu: {len(tekst)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "## 4) Najgorszy przypadek: O(n · m)\n",
    "\n",
    "Dla zwykłego tekstu pierwsza litera zwykle się nie zgadza, więc porównań jest niewiele więcej niż znaków. Ale gdy tekst\n",
    "i wzorzec są „prawie takie same” — np. same litery `a` i wzorzec `aaa…ab` — w każdym oknie porównujesz prawie cały\n",
    "wzorzec: `n · m` porównań."
   ]
  },
  {
   "cell_type": "code",
   "id": "k10",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "zly_tekst = \"a\" * 10_000\n",
    "for m in [2, 10, 50]:\n",
    "    wzorzec = \"a\" * (m - 1) + \"b\"\n",
    "    _, por = naiwne(zly_tekst, wzorzec)\n",
    "    print(f\"m = {m:>2}: {por:>7} porównań (n = {len(zly_tekst)})\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "## 5) Horspool: przeskocz, kiedy możesz\n",
    "\n",
    "Nigel Horspool (1980) uprościł algorytm Boyera i Moore'a (1977). Patrzysz na znak tekstu pod **końcem** okna:\n",
    "- jeśli tego znaku nie ma we wzorcu, wzorzec nie może zaczynać się nigdzie w tym oknie — przeskakujesz o całą długość `m`,\n",
    "- jeśli jest, przesuwasz okno tak, żeby ten znak wypadł pod jego ostatnim wystąpieniem we wzorcu.\n",
    "\n",
    "Przesunięcia liczysz raz, przed szukaniem — to **tabela przesunięć** (zadanie 11.3). Dla dłuższych wzorców algorytm\n",
    "porównuje mniej znaków niż jest w tekście."
   ]
  },
  {
   "cell_type": "code",
   "id": "k12",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def horspool_licz(tekst, wzorzec):\n",
    "    m, n = len(wzorzec), len(tekst)\n",
    "    tabela = {z: m - 1 - i for i, z in enumerate(wzorzec[:-1])}\n",
    "    wynik, porownania, okna, i = [], 0, 0, 0\n",
    "    while i <= n - m:\n",
    "        okna += 1\n",
    "        j = m - 1\n",
    "        while j >= 0:                     # porównujemy od końca okna\n",
    "            porownania += 1\n",
    "            if tekst[i + j] != wzorzec[j]:\n",
    "                break\n",
    "            j -= 1\n",
    "        if j < 0:\n",
    "            wynik.append(i)\n",
    "        i += tabela.get(tekst[i + m - 1], m)\n",
    "    return wynik, porownania, okna\n",
    "\n",
    "poz_h, por_h, okna_h = horspool_licz(tekst, \"Tadeusz\")\n",
    "print(\"wystąpień:\", len(poz_h), \"| porównań:\", por_h, \"| okien:\", okna_h)\n",
    "print(\"te same pozycje co naiwne:\", poz_h == pozycje)\n",
    "print(f\"porównań mniej o {100 * (1 - por_h / por_naiwne):.0f}%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k13",
   "metadata": {},
   "source": [
    "## 6) Czego używa Python: `str.find` i Two-Way\n",
    "\n",
    "`str.find`, `in` i `count` są napisane w C. Krótkie przypadki obsługuje wariant pomysłu Horspoola, a od Pythona 3.10\n",
    "przy dłuższych tekstach CPython przełącza się na algorytm **Two-Way** (Crochemore i Perrin), liniowy także\n",
    "w najgorszym przypadku (zmiana bpo-41972: Dennis Sweeney z Timem Petersem). Do tego dochodzi przewaga C nad pętlą\n",
    "w Pythonie."
   ]
  },
  {
   "cell_type": "code",
   "id": "k14",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "POWTORZENIA = 20                  # find jest tak szybki, że mierzymy średnią\n",
    "start = time.perf_counter()\n",
    "for _ in range(POWTORZENIA):\n",
    "    licznik = 0\n",
    "    i = tekst.find(\"Tadeusz\")\n",
    "    while i != -1:\n",
    "        licznik += 1\n",
    "        i = tekst.find(\"Tadeusz\", i + 1)\n",
    "t_find = (time.perf_counter() - start) / POWTORZENIA\n",
    "print(\"wystąpień:\", licznik, f\"| czas find: {t_find * 1000:.2f} ms\")\n",
    "print(f\"find jest ok. {t_naiwne / t_find:,.0f} razy szybszy niż naiwne\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k15",
   "metadata": {},
   "source": [
    "## 7) Wyrażenia regularne: wzorzec opisany regułą\n",
    "\n",
    "Gdy szukasz nie konkretnego napisu, tylko **kształtu** — „dwie cyfry, myślnik, trzy cyfry” — używasz wyrażeń\n",
    "regularnych (moduł `re`):\n",
    "\n",
    "| Zapis | Znaczy |\n",
    "|---|---|\n",
    "| `\\d` | cyfra |\n",
    "| `\\w` | litera, cyfra albo `_` (także polskie litery) |\n",
    "| `\\b` | granica słowa |\n",
    "| `{2}`, `+`, `*` | dokładnie 2, co najmniej 1, dowolnie wiele |\n",
    "| `[A-Z]` | jeden znak z zakresu |"
   ]
  },
  {
   "cell_type": "code",
   "id": "k16",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import re\n",
    "from collections import Counter\n",
    "\n",
    "adresy = (\"al. Niepodległości 10, 61-875 Poznań; ul. Przykładowa 5, \"\n",
    "          \"00-950 Warszawa; tel. 618561234\")\n",
    "print(re.findall(r\"\\b\\d{2}-\\d{3}\\b\", adresy))\n",
    "\n",
    "print(\"całe słowo Tadeusz:\", len(re.findall(r\"\\bTadeusz\\b\", tekst)))\n",
    "formy = Counter(re.findall(r\"\\bTadeusz\\w*\", tekst))\n",
    "print(formy.most_common(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k17",
   "metadata": {},
   "source": [
    "## 8) Pułapka: katastrofalne nawracanie\n",
    "\n",
    "Silnik `re` przy niepasującym tekście **wraca** i próbuje innych podziałów. Dla wzorca `(a+)+$` i tekstu `aaa…ab`\n",
    "liczba podziałów rośnie wykładniczo: każdy dodatkowy znak mniej więcej podwaja czas.\n",
    "\n",
    "2 lipca 2019 r. nowa reguła zapory sieciowej Cloudflare zawierała wyrażenie regularne, które nawracało tak mocno,\n",
    "że zajęło procesory obsługujące ruch HTTP i HTTPS na całym świecie. Strony za Cloudflare przez ok. 27 minut zwracały\n",
    "błędy.\n",
    "\n",
    "Python 3.11 dodał **kwantyfikatory zaborcze** (`a++`) i grupy atomowe (`(?>…)`): raz dopasowanego fragmentu silnik\n",
    "już nie oddaje, więc nie nawraca."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k18",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** ile razy dłużej potrwa dopasowanie dla tekstu dłuższego o 2 znaki?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Ok. 4 razy: każdy znak mniej więcej podwaja liczbę podziałów do sprawdzenia.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k19",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "for n in [14, 16, 18, 20, 22]:\n",
    "    start = time.perf_counter()\n",
    "    re.match(r\"(a+)+$\", \"a\" * n + \"b\")\n",
    "    print(f\"n = {n}: {(time.perf_counter() - start) * 1000:8.1f} ms\")\n",
    "\n",
    "start = time.perf_counter()\n",
    "re.match(r\"(a++)+$\", \"a\" * 10_000 + \"b\")      # Python 3.11+\n",
    "print(f\"zaborczo, n = 10000: {(time.perf_counter() - start) * 1000:.2f} ms\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k20",
   "metadata": {},
   "source": [
    "## 9) Zadanie 11.0 — wszystkie wystąpienia\n",
    "\n",
    "Napisz `znajdz_wszystkie(tekst, wzorzec)`: lista indeksów **wszystkich** wystąpień, także nakładających się —\n",
    "`znajdz_wszystkie(\"aaaa\", \"aa\")` daje `[0, 1, 2]`. Możesz porównywać wycinki `tekst[i:i + m]`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k21",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def znajdz_wszystkie(tekst: str, wzorzec: str) -> list:\n",
    "    \"\"\"Indeksy wszystkich wystąpień wzorca (także nakładających się).\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k22",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert znajdz_wszystkie(\"aaaa\", \"aa\") == [0, 1, 2]\n",
    "    assert znajdz_wszystkie(\"abrakadabra\", \"abra\") == [0, 7]\n",
    "    assert znajdz_wszystkie(\"abc\", \"x\") == []\n",
    "    assert znajdz_wszystkie(tekst, \"Tadeusz\") == pozycje\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 11.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k23",
   "metadata": {},
   "source": [
    "## Zadanie 11.1 — całe słowa bez względu na wielkość liter\n",
    "\n",
    "Napisz `policz_slowo(tekst, slowo)`: ile razy słowo występuje jako **całe słowo** (nie fragment innego), bez względu\n",
    "na wielkość liter. Użyj `re.findall`, granic słowa `\\b`, `re.escape(slowo)` i flagi `re.IGNORECASE`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k24",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "\n",
    "def policz_slowo(tekst: str, slowo: str) -> int:\n",
    "    \"\"\"Ile razy słowo pada jako całe słowo, bez względu na wielkość liter.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k25",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    zdanie = \"Kot i KOT, a kotlet to nie kot.\"\n",
    "    assert policz_slowo(zdanie, \"kot\") == 3\n",
    "    assert policz_slowo(zdanie, \"kotlet\") == 1\n",
    "    assert policz_slowo(zdanie, \"pies\") == 0\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 11.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k26",
   "metadata": {},
   "source": [
    "## Zadanie 11.2 — kody pocztowe\n",
    "\n",
    "Napisz `kody_pocztowe(tekst)`: lista polskich kodów pocztowych w formacie `00-000`. Napis `61-8561234` zaczyna się\n",
    "jak kod, ale dalej są cyfry — nie powinien się złapać. Pomogą granice słowa `\\b`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k27",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "\n",
    "def kody_pocztowe(tekst: str) -> list:\n",
    "    \"\"\"Polskie kody pocztowe w formacie 00-000.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k28",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert kody_pocztowe(adresy) == [\"61-875\", \"00-950\"]\n",
    "    assert kody_pocztowe(\"tel. 61-8561234, kod 60-967\") == [\"60-967\"]\n",
    "    assert kody_pocztowe(\"brak\") == []\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 11.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k29",
   "metadata": {},
   "source": [
    "## Zadanie 11.3 — tabela przesunięć Horspoola\n",
    "\n",
    "Napisz `tabela_przesuniec(wzorzec)`: słownik `znak → przesunięcie` dla wszystkich znaków wzorca **oprócz ostatniego**.\n",
    "Przesunięcie to `m − 1 − i`, gdzie `i` to **ostatnia** pozycja znaku w `wzorzec[:-1]`. Znaków spoza słownika\n",
    "algorytm przesuwa o `m`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k30",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def tabela_przesuniec(wzorzec: str) -> dict:\n",
    "    \"\"\"Horspool: o ile przesunąć okno, gdy pod jego końcem stoi dany znak.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k31",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert tabela_przesuniec(\"ABRA\") == {\"A\": 3, \"B\": 2, \"R\": 1}\n",
    "    assert tabela_przesuniec(\"Tadeusz\") == {\n",
    "        \"T\": 6, \"a\": 5, \"d\": 4, \"e\": 3, \"u\": 2, \"s\": 1}\n",
    "    assert tabela_przesuniec(\"x\") == {}\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 11.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k32",
   "metadata": {},
   "source": [
    "## Zadanie 11.4 dla chętnych — Horspool\n",
    "\n",
    "Napisz `horspool(tekst, wzorzec)`, który zwraca listę wszystkich wystąpień, używając swojej tabeli z zadania 11.3.\n",
    "W każdym oknie sprawdź wycinek, a potem przesuń okno o `tabela.get(tekst[i + m - 1], m)`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k33",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def horspool(tekst: str, wzorzec: str) -> list:\n",
    "    \"\"\"Wszystkie wystąpienia wzorca algorytmem Boyera–Moore'a–Horspoola.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k34",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert horspool(\"abrakadabra\", \"abra\") == [0, 7]\n",
    "    assert horspool(tekst, \"Tadeusz\") == pozycje\n",
    "    assert horspool(tekst, \"Zosia\") == naiwne(tekst, \"Zosia\")[0]\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 11.4 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k35",
   "metadata": {},
   "source": [
    "## Zapamiętaj\n",
    "\n",
    "- Naiwnie: okno przesuwane o 1 znak, najgorzej O(n · m). W zwykłym tekście zwykle szybko odpada na pierwszej literze.\n",
    "- Horspool: tabela przesunięć i skoki o kilka znaków — mniej porównań dla dłuższych wzorców.\n",
    "- `in`, `find`, `count` są w C i od Pythona 3.10 używają Two-Way — w praktyce używaj ich.\n",
    "- Wyrażenia regularne opisują **kształt** tekstu. Unikaj zagnieżdżonych powtórzeń typu `(a+)+` — albo użyj `a++`.\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Ile razy w „Panu Tadeuszu” pada „Zosia”, a ile „Zosię”, „Zosi”, „Zosią”? Napisz jedno wyrażenie na wszystkie formy.\n",
    "2. Dla jakiego wzorca Horspool przeskakuje najdalej? Sprawdź licznikiem okien.\n",
    "3. Znajdź w tekście wszystkie liczby rzymskie (np. „Księga I”) wyrażeniem regularnym."
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}