Łańcuchy znakowe


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie

 

Współczesne komputery oprócz liczb przetwarzają również teksty. Teksty zbudowane są z ciągów znakowych, które możemy traktować jako tablice znaków – dostęp do poszczególnych liter odbywa się, podobnie jak u tablic, poprzez indeks, czyli numer znaku w ciągu. W rzeczywistości znak przechowywany jest w pamięci komputera w postaci liczby – kodu znaku. Rozróżniamy dwa rodzaje takich kodów – 8 bitowe (najczęściej są to znormalizowane kody wg standardu ASCII – ang. American Standard Code for Information Interchange – Amerykański Standardowy Kod do Wymiany Informacji) i 16 bitowe (standard Unicode). Znaki 16 bitowe wprowadzono w celu ominięcia ograniczeń kodów 8 bitowych, które mogą reprezentować jedynie do 256 różnych znaków, co jest niewystarczające do reprezentowania wszystkich znaków narodowych oraz różnych symboli stosowanych w matematyce, fizyce i innych dziedzinach ludzkiej działalności.

Jednym z podstawowych problemów znakowych jest problem wyszukiwania wzorca (ang. pattern searching lub patterrn matching) – tzn. mając dany pewien ciąg znaków szukamy w innym ciągu znakowym miejsca, w którym występuje ciąg pierwszy. Taki problem często występuje podczas redagowania tekstów, gdy w większym tekście należy wyszukać określoną frazę. Informatycy poświęcili wiele pracy na rozwiązanie tego podstawowego problemu. W efekcie wynaleziono bardzo efektywne algorytmy wyszukiwania wzorca, które znajdują zastosowania również przy rozwiązywaniu innych problemów tekstowych.

W tym rozdziale zajmiemy się algorytmami przetwarzania danych tekstowych. Wiele z nich można z powodzeniem wykorzystywać na różnych konkursach programowania oraz na olimpiadach informatycznych. Zapraszamy do lektury.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.