Podsłowo – spójny podciąg znaków danego łańcucha znaków.
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:
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 [1].
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[2].
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 [1].
Jeśli i są niepuste to jest nazywany sufiksem właściwym[2].
Przykładowo,
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.