Algorytmy tekstowe
Kody ASCII, zliczanie liter, palindromy, prefiksy i sufiksy, porównywanie słów.
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: .
- 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 od 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.
Średnie zadania
Pary słów. W pliku pary.txt znajduje się 500 par słów złożonych z małych liter alfabetu angielskiego; każda para w osobnym wierszu, słowa oddzielone spacją (długość słowa ≤ 50). Pliki z danymi (Dane-NF-2605.zip) pobierzesz na stronie arkusza.
Niech oznacza sumę kodów ASCII znaków słowa . Podaj parę słów z jednego wiersza, dla której jest największa, oraz tę wartość (jest tylko jedna taka para).
Przykład: , , różnica . Dla pary_przyklad.txt odpowiedź to: eddcd eededcddceeecededcc 1403.
Wpisz: słowo1 słowo2 wartość.
Wspólną liczbę wystąpień litery w słowach oznaczamy , gdzie to liczba wystąpień litery w .
Podaj parę słów z jednego wiersza pliku pary.txt, dla której suma wspólnych wystąpień wszystkich liter jest największa, oraz tę sumę (jest jedna taka para).
Przykład: dla pary adabbcdde aadabbbccdc suma wynosi . Dla pary_przyklad.txt odpowiedź: ccccdcedddddecde ccdcdddecc 10.
Wpisz: słowo1 słowo2 suma.
Trudne zadania
Prefiksosufiksem pary słów nazywamy słowo, które jest początkiem i końcem albo początkiem i końcem .
Podaj wszystkie pary słów z pliku pary.txt, dla których najdłuższy prefiksosufiks ma co najmniej 5 liter, i dla każdej podaj długość najdłuższego prefiksosufiksu.
Przykłady: dla aabbbca caacaab najdłuższy prefiksosufiks ma długość 3 (aab, ca); dla abbaabaa baabaabba — 6 (baabaa). Dla pary_przyklad.txt poprawna odpowiedź: ececdddeed dddeedd 6.
W pliku symbole.txt szukamy „kwadratów” złożonych z dziewięciu sąsiadujących identycznych symboli (kwadrat 3×3 z tych samych znaków: +, o albo *). Napisy (wiersze) mają 12 znaków. Podaj, ile takich kwadratów występuje, oraz numer wiersza i numer pozycji w wierszu (od 1) środkowego pola każdego z nich.
Przykład: dla symbole_przyklad.txt odpowiedź to 1 6 3 (jeden kwadrat o środku w wierszu 6, na pozycji 3).
Wpisz: liczba_kwadratów, a potem pary wiersz pozycja dla każdego kwadratu (wszystko oddzielone spacjami, w kolejności wierszy).