Podsłowo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja[edytuj | edytuj kod]

Dla danego słowa t = x_1 x_2 x_3 \ldots x_n podsłowem t nazywamy słowo

s = x_{i+1} x_{i+2} \ldots x_{i+m},

dla pewnych liczb i i m takich, że 0 \leqslant i \land i+m \leqslant n. Jeżeli dodatkowo m\neq 0 (czyli s\neq\varepsilon) oraz m\neq n (s \neq t), 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:

b\underline{an\overline{a}}\overline{na}

Szczególne podsłowa[edytuj | edytuj kod]

Prefiks[edytuj | edytuj kod]

Zobacz hasło prefiks w Wikisłowniku

Słowo s jest prefiksem słowa t wtedy i tylko wtedy, kiedy istnieje słowo y takie, że t = sy, gdzie sy oznacza konkatenację słów s i y. Taką relację oznaczamy s \sqsubset t[1]. Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: s \sqsubset t wtedy i tylko wtedy, gdy t = x_1 x_2 x_3 \ldots x_n, a s = x_1 x_2 x_3 \ldots x_j dla pewnego j \in \lbrace0, \ldots, n\rbrace.

Przykładowo, ban \sqsubset \underline{ban}ana.

Sufiks[edytuj | edytuj kod]

Zobacz hasło sufiks w Wikisłowniku

Słowo s jest sufiksem słowa t wtedy i tylko wtedy, kiedy istnieje słowo y takie, że t = ys. Oznaczamy wtedy s \sqsupset t[1].

Przykładowo, na \sqsupset bana\underline{na}.

Prefikso-sufiks[edytuj | edytuj kod]

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. 1,0 1,1 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 | edytuj kod]