ASD Ćwiczenia 14

Zadanie 1

Dane są teksty x, y. Oblicz najdłuższy tekst $z$ (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 $lcp$ będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech $SUMA(lcp)$ będzie sumą elementów tablicy $lcp$. Uzasadnij, dlaczego liczba wszystkich niepustych podsłów x wynosi

$(\genfrac{}{}{0ex}{}{n+1}{2})-SUMA(lcp)$

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 $lcp$.

Zadanie 3

Wyprowadź wzór na $|Subwords(F_n)|$

Rozwiązanie

Oznaczmy $Sub(n)=|Subwords(F_n)|$ i niech ${\mathrm{\Phi }}_n$ będzie n-tą liczba Fibonacciego. Wtedy

$Sub(n+1)=Sub(n)+{\mathrm{\Phi }}_{n-3}\cdot {\mathrm{\Phi }}_{n-1}+{\mathrm{\Phi }}_{n-2}\cdot ({\mathrm{\Phi }}_{n-1}+2)$ Parser nie mógł rozpoznać (błąd składni): {\displaystyle {Sub(n)\ =\ \Phi_{n-1}\Phi_{n-2}+2\cdot \Phi_{n-1}-1}

Zadanie 4

Niech $lc{p}^{\prime }[k]=lcp[rank[k]-1]$. Udowodnij, że $lc{p}^{\prime }[k]\ge lc{p}^{\prime }[k-1]-1$

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.