Podsłowo

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

Definicja

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

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

Prefiks

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

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

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

Prefikso-sufiks

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

Zobacz też

• język formalny
• podciąg
• algorytm Knutha-Morrisa-Pratta
• drzewo sufiksowe