Podsłowo – spójny podciąg znaków danego łańcucha znaków.

Definicja formalnaEdytuj

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ładEdytuj

Dla słowa banana, ana jest równe dwóm podsłowom rozpoczynającym się na dwóch różnych pozycjach:

 

Szczególne podsłowaEdytuj

PrefiksEdytuj

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,  

SufiksEdytuj

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-sufiksEdytuj

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

PrzypisyEdytuj

  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].