Tekst źródłowy strony Podsłowo

{{Inne znaczenia|informatyki|[[Przyrostek|sufiks w językoznawstwie]]}}

'''Podsłowo''' – spójny [[podciąg (matematyka)|podciąg]] znaków danego [[Tekstowy typ danych|łańcucha znaków]].

== Definicja formalna ==
Dla danego [[język formalny|słowa]] <math>t = x_1 x_2 x_3 \ldots x_n</math> '''podsłowem''' <math>t</math> nazywamy słowo:
: <math>s = x_{i+1} x_{i+2} \ldots x_{i+m},</math>

dla pewnych liczb <math>i</math> i <math>m</math> takich, że <math>0 \leqslant i \land i+m \leqslant n.</math>

Jeżeli dodatkowo <math>m\neq 0</math> (czyli <math>s\neq\varepsilon</math>) oraz <math>m\neq n</math> <math>(s \neq t),</math> to takie podsłowo nazywamy '''właściwym'''.

Relacja bycia podsłowem (a zatem również relacje bycia prefiksem i bycia sufiksem) jest [[relacja zwrotna|zwrotna]], [[relacja przechodnia|przechodnia]] i [[relacja antysymetryczna|antysymetryczna]], jest więc [[częściowy porządek|słabym porządkiem częściowym]].

=== Przykład ===
Dla słowa ''banana'', ''ana'' jest równe dwóm podsłowom rozpoczynającym się na dwóch różnych pozycjach:
: <math>b\underline{an\overline{a}}\overline{na}</math>

== Szczególne podsłowa ==
=== Prefiks ===
{{wikisłownik|prefiks}}
Słowo <math>s</math> jest '''prefiksem''' słowa <math>t</math> wtedy i tylko wtedy, kiedy istnieje słowo <math>y</math> takie, że <math>t = sy,</math> gdzie <math>sy</math> oznacza [[konkatenacja|konkatenację]] słów <math>s</math> i <math>y.</math> Taka [[relacja (matematyka)|relacja]] oznaczana jest poprzez <math>s \sqsubset t</math><ref name="corm">{{Cytuj książkę |autor = Diks, Krzysztof; Cormen, Thomas H |tytuł = Wprowadzenie do algorytmów |data = 2007 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 978-83-204-3328-9 |strony = 930}}</ref>.

Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: <math>s \sqsubset t</math> wtedy i tylko wtedy, gdy <math>t = x_1 x_2 x_3 \ldots x_n,</math> a <math>s = x_1 x_2 x_3 \ldots x_j</math> dla pewnego <math>j \in \{0, \dots, n\}.</math>

Jeśli <math>s</math> i <math>y</math> są niepuste to <math>s</math> jest nazywany prefiksem właściwym<ref name="Grządko" />.

Przykładowo, <math>ban \sqsubset \underline{ban}ana.</math>

=== Sufiks ===
{{wikisłownik|sufiks}}
Słowo <math>s</math> jest '''sufiksem''' słowa <math>t</math> wtedy i tylko wtedy, kiedy istnieje słowo <math>y</math> takie, że <math>t = ys.</math> Relacja ta oznaczana jest wtedy poprzez <math>s \sqsupset t</math><ref name="corm" />.

Jeśli <math>s</math> i <math>y</math> są niepuste to <math>s</math> jest nazywany sufiksem właściwym<ref name="Grządko" />.

Przykładowo, <math>na \sqsupset bana\underline{na}.</math>

=== Prefikso-sufiks ===
Właściwy prefiks danego słowa, który jest równy jego sufiksowi, nazywamy '''prefikso-sufiksem'''<ref>{{cytuj stronę |url = http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Algorytmy_tekstowe_I |tytuł = Algorytmy tekstowe I |autor = Diks, K |autor2 = Malinowski, A |autor3 = Rytter, W |autor4 = Waleń, T |praca = Algorytmy i struktury danych |data dostępu = 2008-05-02}}</ref>. Znajdowanie prefikso-sufiksów tekstu jest kluczowe dla [[algorytm Knutha-Morrisa-Pratta|algorytmu Knutha-Morrisa-Pratta]] wyszukiwania wystąpień wzorca w tekście.

== Zobacz też ==
* [[algorytm Knutha-Morrisa-Pratta]]
* [[drzewo sufiksowe]]
* [[język formalny]]
* [[podciąg (matematyka)|podciąg]]

== Przypisy ==
{{Przypisy
|Grządko={{Cytuj |autor = Łukasz Grządko |url = http://www.deltami.edu.pl/temat/informatyka/algorytmy/2014/12/28/O_rozkladzie_slow_na_slowa_Lyndo/ |tytuł = O rozkładzie słów na słowa Lyndona |czasopismo = Delta |data = styczeń 2015 |data dostępu = 2018-06-27 |s = 9}}
}}

{{Teoria porządku}}

[[Kategoria:Języki formalne]]
[[Kategoria:Algorytmy tekstowe]]
[[Kategoria:Dwuczłonowe relacje matematyczne]]
[[Kategoria:Relacje dwuczłonowe w językoznawstwie]]