Nauka / Algorytmy tekstowe

Algorytmy tekstowe

Kody ASCII, zliczanie liter, palindromy, prefiksy i sufiksy, porównywanie słów.

Rozszerzony

Teoria, wzory i przykłady

Kodowanie znaków

Znak ma kod ASCII (a = 97, A = 65, 0 = 48). Suma kodów słowa to suma kodów jego liter. W Pythonie: ord('a') = 97, chr(97) = 'a'.

Podstawowe operacje

  • Zliczanie liter: tablica 26 liczników lub słownik.
  • Wspólna liczba wystąpień liter w dwóch słowach: ∑xmin⁡(d(x,s1),d(x,s2))\sum_x\min(d(x,s_1),d(x,s_2)).
  • Palindrom: słowo równe swemu odwróceniu.
  • Prefiks/sufiks: początek/koniec słowa; prefiksosufiks pary słów to słowo będące początkiem jednego i końcem drugiego.

Wzorzec zadania „pary słów z pliku”

with open("pary.txt") as f:
    for linia in f:
        s1, s2 = linia.split()
        # oblicz wartość dla pary, zapamiętaj najlepszą

Najdłuższy prefiksosufiks: sprawdź kolejne długości kk od min⁡(∣s1∣,∣s2∣)\min(|s_1|,|s_2|) w dół i porównaj s1[:k] z s2[-k:] oraz s2[:k] z s1[-k:].

Wskazówki

  • Zawsze sprawdź program na pliku przykładowym z arkusza i porównaj z podaną odpowiedzią.
  • Pamiętaj o formacie odpowiedzi: numer zadania, potem wynik.

Łatwe zadania

Średnie zadania

Trudne zadania

Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.
Test działowy