W tym przypadku konieczne jest zakończenie każdego ze słów unikalnym znakiem lub słowem.
Zastosowania Drzewa sufiksowe znajdują zastosowanie między innymi w bioinformatyce, gdzie służą do analizy łańcuchów DNA i sekwencji aminokwasów w białkach, oraz w kompresji danych (modyfikacje kompresji LZW).
Funkcjonalności Drzewo sufiksowe dla słowa długości i uogólnione drzewo sufiksowe dla słów o łącznej długości można zbudować w czasie Po zbudowaniu może służyć między innymi do efektywnego wykonania następujących operacji: znajdowanie dowolnego wystąpienia wzorca P długości jako podsłowa słowa S w czasie znajdowanie wszystkich wystąpień wzorca P długości w słowie S w czasie znajdowanie najdłuższego wspólnego podsłowa (spójnego podciągu) dwóch napisów długości i w czasie znajdowanie najdłuższego podsłowa słowa S które powtarza się w tym słowie w czasie
Szczegóły implementacji Drzewo sufiksowe można przechowywać w pamięci rozmiaru liniowego względem długości słowa S, utrzymując jako etykiety krawędzi drzewa pozycje początkowego i końcowego znaku etykiety zamiast wszystkich jej znaków.
Zobacz też algorytm Knutha-Morrisa-Pratta – inna metoda szybkiej implementacji działań na łańcuchach znaków skompresowane drzewo trie
Przypisy
Bibliografia
Linki zewnętrzne Wizualizacja drzewa sufiksowego
Sufiksowe, drzewo Kategoria:Algorytmy tekstowe