Podsłowo

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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]

  1. a b Diks, Krzysztof; Cormen, Thomas H: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 930. ISBN 978-83-204-3328-9.
  2. a b Łukasz Grządko, O rozkładzie słów na słowa Lyndona, „Delta”, styczeń 2015, s. 9 [dostęp 2018-06-27].
  3. Diks, K, Malinowski, A, Rytter, W, Waleń, T: Algorytmy tekstowe I. W: Algorytmy i struktury danych [on-line]. [dostęp 2 maja 2008].