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