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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 81: Linia 81:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Tablica  sufiksowa dla słowa compress(x) składa się z dwóch ''połówek'', kodują one ślowa zaczynające się na pozycjach  
+
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.  
 
odpowiedni i mod 3 =1, oraz i mod 3 =2.  
 
</div>
 
</div>
 
</div>
 
</div>

Wersja z 09:31, 12 wrz 2006

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

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

Policz wzór na

Rozwiązanie


Zadanie 4

Niech . Udowodnij, że

Rozwiązanie

Zadanie 5

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

Rozwiązanie

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