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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
=='''Zadanie 1'''==
 
=='''Zadanie 1'''==
 
 
Dane sa teksty x, y, oblicz najdłuższy tekst z (który oznaczamy LCS(x,y) od ang. Longest Common Subword)
 
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.
+
który jest jednocześnie podsłowem x, y.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 14: Linia 13:
 
  </div>
 
  </div>
 
</div>
 
</div>
 
 
  
 
=='''Zadanie 2'''==
 
=='''Zadanie 2'''==

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