Podsłowo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja formalna[edytuj]

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]

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]

Prefiks[edytuj]

Słowo jest prefiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że , gdzie oznacza konkatenację słów i . Taką relację oznaczamy [1]. Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: wtedy i tylko wtedy, gdy , a dla pewnego .

Przykładowo, .

Sufiks[edytuj]

Słowo jest sufiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że . Oznaczamy wtedy [1].

Przykładowo, .

Prefikso-sufiks[edytuj]

Właściwy prefiks danego słowa, który jest równy jego sufiksowi, nazywamy prefikso-sufiksem[2]. Znajdowanie prefikso-sufiksów tekstu jest kluczowe dla algorytmu Knutha-Morrisa-Pratta wyszukiwania wystąpień wzorca w tekście.

Przypisy

  1. a b Diks, Krzysztof; Cormen, Thomas H: Wprowadzenie do algorytmów. Warszawa: Wydawnictwo Naukowo-Techniczne, 2007, s. 930. ISBN 978-83-204-3328-9.
  2. Diks, K., Malinowski, A., Rytter, W.: Algorytmy tekstowe I. W: Algorytmy i struktury danych [on-line]. [dostęp 2 maja 2008].

Zobacz też[edytuj]