Podsłowo – spójny podciąg znaków danego łańcucha znaków.
Definicja formalna Dla danego słowa podsłowem nazywamy słowo:
dla pewnych liczb i takich, że
Jeżeli dodatkowo (czyli ) oraz 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:
Szczególne podsłowa Prefiks
Słowo jest prefiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że gdzie oznacza konkatenację słów i Taka relacja oznaczana jest poprzez .
Równoważna definicja zgodna z powyższą definicją podsłowa jest następująca: wtedy i tylko wtedy, gdy a dla pewnego
Jeśli i są niepuste to jest nazywany prefiksem właściwym.
Przykładowo,
Sufiks
Słowo jest sufiksem słowa wtedy i tylko wtedy, kiedy istnieje słowo takie, że Relacja ta oznaczana jest wtedy poprzez .
Jeśli i są niepuste to jest nazywany sufiksem właściwym.
Przykładowo,
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
Przypisy
Kategoria:Języki formalne Kategoria:Algorytmy tekstowe Kategoria:Dwuczłonowe relacje matematyczne Kategoria:Relacje dwuczłonowe w językoznawstwie