Podsłowo – spójny podciąg znaków danego łańcucha znaków.
Definicja formalna
[edytuj | edytuj kod]Dla danego słowa podsłowem nazywamy słowo:
dla pewnych liczb i takich, że
Jeżeli dodatkowo (czyli ) oraz to takie podsłowo nazywamy właściwym.
Relacja bycia podsłowem (a zatem również relacje bycia prefiksem i bycia sufiksem) jest zwrotna, przechodnia i antysymetryczna, jest więc słabym porządkiem częściowym.
Przykład
[edytuj | edytuj kod]Dla słowa banana, ana jest równe dwóm podsłowom rozpoczynającym się na dwóch różnych pozycjach:
Szczególne podsłowa
[edytuj | edytuj kod]Prefiks
[edytuj | edytuj kod]Słowo jest prefiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że gdzie oznacza konkatenację słów i Taka relacja oznaczana jest poprzez [1].
Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: wtedy i tylko wtedy, gdy a dla pewnego
Jeśli i są niepuste to jest nazywany prefiksem właściwym[2].
Przykładowo,
Sufiks
[edytuj | edytuj kod]Słowo jest sufiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że Relacja ta oznaczana jest wtedy poprzez [1].
Jeśli i są niepuste to jest nazywany sufiksem właściwym[2].
Przykładowo,
Prefikso-sufiks
[edytuj | edytuj kod]Właściwy prefiks danego słowa, który jest równy jego sufiksowi, nazywamy prefikso-sufiksem[3]. Znajdowanie prefikso-sufiksów tekstu jest kluczowe dla algorytmu Knutha-Morrisa-Pratta wyszukiwania wystąpień wzorca w tekście.
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ a b Diks, Krzysztof; Cormen, Thomas H: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 930. ISBN 978-83-204-3328-9.
- ↑ a b Łukasz Grządko , O rozkładzie słów na słowa Lyndona, „Delta”, styczeń 2015, s. 9 [dostęp 2018-06-27] .
- ↑ Diks, K, Malinowski, A, Rytter, W, Waleń, T: Algorytmy tekstowe I. [w:] Algorytmy i struktury danych [on-line]. [dostęp 2008-05-02].