Podsłowo

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

Definicja formalna

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.$ Taka relacja oznaczana jest poprzez $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 \{0,\dots ,n\}.$

Jeśli $s$ i $y$ są niepuste to $s$ jest nazywany prefiksem właściwym.

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.$ Relacja ta oznaczana jest wtedy poprzez $s\sqsupset t$.

Jeśli $s$ i $y$ są niepuste to $s$ jest nazywany sufiksem właściwym.

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ż

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