ASD Ćwiczenia 14: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 18: Linia 18:
 
Niech <math>lcp</math> będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech
 
Niech <math>lcp</math> będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech
 
<math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Uzasadnij, dlaczego liczba  
 
<math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Uzasadnij, dlaczego liczba  
wszystkich niepustych podsłów x wynosi
+
wszystkich niepustych podsłów x wynosi
  
  

Wersja z 14:15, 30 wrz 2006

Zadanie 1

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