Podsłowo

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

Definicja formalna

Dla danego słowa ${\displaystyle t=x_{1}x_{2}x_{3}\ldots x_{n}}$ podsłowem ${\displaystyle t}$ nazywamy słowo:

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

dla pewnych liczb ${\displaystyle i}$ i ${\displaystyle m}$ takich, że ${\displaystyle 0\leqslant i\land i+m\leqslant n.}$

Jeżeli dodatkowo ${\displaystyle m\neq 0}$ (czyli ${\displaystyle s\neq \varepsilon }$) oraz ${\displaystyle m\neq n}$ ${\displaystyle (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:

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

Szczególne podsłowa

Prefiks

Słowo ${\displaystyle s}$ jest prefiksem słowa ${\displaystyle t}$ wtedy i tylko wtedy, kiedy istnieje słowo ${\displaystyle y}$ takie, że ${\displaystyle t=sy,}$ gdzie ${\displaystyle sy}$ oznacza konkatenację słów ${\displaystyle s}$ i ${\displaystyle y.}$ Taka relacja oznaczana jest poprzez ${\displaystyle s\sqsubset t}$^[1].

Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: ${\displaystyle s\sqsubset t}$ wtedy i tylko wtedy, gdy ${\displaystyle t=x_{1}x_{2}x_{3}\ldots x_{n},}$ a ${\displaystyle s=x_{1}x_{2}x_{3}\ldots x_{j}}$ dla pewnego ${\displaystyle j\in \lbrace 0,\dots ,n\rbrace .}$

Jeśli ${\displaystyle s}$ i ${\displaystyle y}$ są niepuste to ${\displaystyle s}$ jest nazywany prefiksem właściwym^[2].

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

Sufiks

Słowo ${\displaystyle s}$ jest sufiksem słowa ${\displaystyle t}$ wtedy i tylko wtedy, kiedy istnieje słowo ${\displaystyle y}$ takie, że ${\displaystyle t=ys.}$ Relacja ta oznaczana jest wtedy poprzez ${\displaystyle s\sqsupset t}$^[1].

Jeśli ${\displaystyle s}$ i ${\displaystyle y}$ są niepuste to ${\displaystyle s}$ jest nazywany sufiksem właściwym^[2].

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

Prefikso-sufiks

Właściwy prefiks danego słowa, który jest równy jego sufiksowi, nazywamy prefikso-sufiksem^[3]. 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

Przypisy