ASD Ćwiczenia 14

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Dane są 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

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


Zadanie 3

Wyprowadź wzór na

Rozwiązanie

Zadanie 4

Niech . Udowodnij, że

Rozwiązanie

Zadanie 5

Opisz liniowy algorytm obliczania tablicę ROT, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.

Rozwiązanie

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


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 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


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