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\dots x_n$ podsłowem $t$ nazywamy słowo:

$s=x_{i+1}{x}_{i+2}\dots x_{i+m},$

dla pewnych liczb $i$ i $m$ takich, że $0⩽i\wedge i+m⩽n.$

Jeżeli dodatkowo $m\ne 0$ (czyli $s\ne \epsilon$) oraz $m\ne n$ $(s\ne 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\underset{\_}{an\bar{a}}\overline{na}$

Szczególne podsłowa

Prefiks

Szablon:Wikisłownik 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⊏t$.

Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: $s⊏t$ wtedy i tylko wtedy, gdy $t=x_1{x}_2{x}_3\dots x_n,$ a $s=x_1{x}_2{x}_3\dots 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⊏\underset{\_}{ban}ana.$

Sufiks

Szablon:Wikisłownik 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⊐t$.

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

Przykładowo, $na⊐bana\underset{\_}{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