Zadanie 1
Dane sa teksty x, y, oblicz najdłuższy tekst
(oznaczany LCS(x,y) od ang. Longest Common Subword),
który jest jednocześnie podsłowem x i y.
Rozwiązanie
Konstruujemy drzewo sufiksowe dla tekstu x#y$. LCS(x,y) odpowiada węzłowi w drzewie, który
reprezentuje najdłuższe podsłowo, oraz z którego prowadzą ścieżki do liści reprezentujących numer sufiksu zaczynającego
się w x, i numer sufiksu zaczynającego się w y. Drzewo trzeba odpowiednio wstępnie przetworzyć bottom-up, żeby
można było potem łatwo wyliczyć odpowiedni węzeł. Podobnie rozwiązujemy problem dla wielu słów x,y ,.. .
Zadanie 2
Niech
będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech
będzie sumą elementów tablicy
. Uzasadnij, dlaczego liczba
wszystkich niepustych podsłów x wynosi
Rozwiązanie
Liczba ta jest równa sumie wag krawędzi drzewa sufiksowego. Wzór z zadania wynika z konstrukcji drzewa
sufiksowego opierającej się na tablicy sufiksowej i tablicy
.
Zadanie 3
Wyprowadź wzór na
Zadanie 4
Niech
.
Udowodnij, że
Rozwiązanie
Wynika to ze struktury tablicy lcp oraz z tego, że kolejno rozważane słowa powstają z poprzednich
przez obcięcie pierwszej litery.
Zadanie 5
Opisz liniowy algorytm obliczania tablicę ROT, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.
Rozwiązanie
Zastosuj algorytm obliczania tablicy sufiksowej do słowa xx.
Zadanie 6
Pokaż, że jeśli mamy tablicę sufiksową dla słowa compress(x), to można łatwo obliczyć SUF[M] w czasie liniowym.
Rozwiązanie
Tablica sufiksowa dla słowa compress(x) składa się z dwóch połówek, kodują one słowa zaczynające się na pozycjach
odpowiedni i mod 3 =1, oraz i mod 3 =2.