ASD Ćwiczenia 14

Zadanie 1

Dane sa teksty x, y, oblicz najdłuższy tekst z (który oznaczamy LCS(x,y) od ang. Longest Common Subword) który jest jednocześnie podsłowem x, y.

Rozwiązanie

Konstruujemy drzewo sufiksowe dla tekstu x#y$. nwpodsłowo(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 przeprocessować bottom-up, żeby można było potem łatwo wyliczyć odpowiedni węzeł. Podobnie rozwiazujemy dla wiely 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

${n+1 \choose {2}}-SUMA(lcp)$

Rozwiązanie

Liczba ta jest równa sumie wag krawędzi drzewa sufiksowego. Wzór z zadania wynika to z konstrukcji drzewa sufiksowego opiuerającej się na tablicy sufiksowej i tablicy $lcp$.

Zadanie 3

Policz wzór na $|Subwords(F_{n})|$

Rozwiązanie

Oznaczmy $Sub(n)=|Subwords(F_{n})|$, niech $\Phi _{n}$ będzie n-tą liczba Fibonacciego. Wtedy

$Sub(n+1)\ =\ Sub(n)+\Phi _{n-3}\cdot \Phi _{n-1}+\Phi _{n-2}\cdot (\Phi _{n-1}+2)$ Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle {Sub(n)\ =\ \Phi_{n-1}\Phi_{n-2}+2\cdot \Phi_{n-1}-1}

Zadanie 4

Niech $lcp'[k]\ =\ lcp[rank[k]-1]$. Udowodnij, że $lcp'[k]\geq lcp'[k-1]-1$

Rozwiązanie

Wynika ze struktury tablicy lcp, oraz stąd że kolejno rozważane słow powstają z poprzednich przez obcięcie pierwszej litery.

Zadanie 5

Opisz liniowy algorytm liczący tablicę ROT, zakładając, że mamy liniowy algorytm liczenia tablicy sufiksowej.

Rozwiązanie

Zastosuj algorytm na liczenie tablicy sufiksowej do słowa xx

Zadanie 6

Pokaż, że jeśli mamy tablicę sufiksową dla słowa compress(x) to można łatwo policzyć 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.