Ćwiczenia | Informatyka MIMUW

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

$ {n+1\choose{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 $ \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) $
$ 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]\ge lcp'[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.

Zadanie 7

(Teksty-> Grafy) Dany jet zbiór tekstów długości dwa. Wyznaczyć długość minimalnego tekstu, zawierającego teksty wejściowe.

Rozwiązanie

Zadanie sprowadza się do policzenia minimalnego ( w sensie liczności) zbioru rozłącznych ścieżek w grafie skierowanym, które zawierają wszystkie krawędzie. Krawędzie odpowiadają słowom wejściowym, wierzchołki grafu odpowiadają literom.

Zadanie było na olimpiadzie informatycznej pod nazwą Pierwotek abstrakcyjny, miało rozwiązanie w czasie liniowym.

Zadanie 8

Dany jest zbiór X tekstów binarnych. Sprawdzić czy istnieje nieskończenie wiele słów binarnych nie zawierających żadnego elementu z X jako podsłowo.

Rozwiązanie

Opiszemy operacje redukcji tekstu. Jeśli w zbiorze X są teksty ua, vb, gdzie a,b są różnymi cyframi binarnymi oraz u jest sufiksem v (np. gdy $ u=v $) , to zastępujemy w X słowo vb przez słowo v. Inaczej mówiąc wykonujemy operację:

redukcja: vb -> v

Algorytm wykonuje wszelkie redukcje póki się da (w dowolnym porządku). Jeśli otrzymamy słowo puste to odpowiedź jest NIE, w przeciwym wypadku TAK.

Zadanie było na olimpiadzie informatycznej pod nazwą Wirusy, miało rozwiązanie w czasie liniowym.

Zadanie 9

Udowdnij, że dla słów Fibonacciego kończących się na literę 'a' tablica sufksowa jest postępem arytmetycznym modulo długość słowa.

Rozwiązanie

Zobacz jakie są zależności między słowami Fibonacciego i zapisem kolejnych liczb naturalnych w systemie liczbowym Fibonacciego.