Zaawansowane algorytmy i struktury danych/Ćwiczenia 3: Różnice pomiędzy wersjami

Wersja z 12:22, 12 wrz 2006

Udwodnij, że jeśli $L Z (x) = (v_{1}, v_{2}, \dots, v_{m})$ to x zawiera powtórzenie uu wtedy i tylko wtedy gdy dla pewnego k zachodzi

R i g h t T e s t (v_{1}, v_{2} \dots v_{k - 2}, v_{k - 1} v_{k} l u b R i g h t t e s t (v_{1}, v_{2} \dots v_{k - 1}, v_{k})

Rozwiązanie

.

Jeśli środek powtórzenia byłby wcześniej to $v_{k}$ by nie występowało w faktoryzacji.

Oblicz faktoryzację LZ(x) w czasei liniowym.

Rozwiązanie

Udowdnij, ze algorytm Szukanie-Powtórzeń dziła w czasie liniowym.

Rozwiązanie

.

Złożoność liczenia alternatywy RightTest(u1,v1) lub RightTest(u2,v2) jest $O (| v_{k - 1} v_{k} |)$ , oraz zachodzi

\sum_{k = 1}^{m} | v_{k - 1} v_{k} | \leq 2 n

Udowodnij własność parzystych palstarów:

$x [i . . n] \in P A L_{0}^{*} \Rightarrow p a r s e_{0} (i) = f i r s t_{0} (i)$

Rozwiązanie

Udowdnij, własność dowolnych palstarów:

$x [i . . n] \in P A L^{*} \Rightarrow p a r s e (i) \in {f i r s t (i), 2 \cdot f i r s t (i) + 1, 2 \cdot f i r s t (i) - 1}$

Rozwiązanie

@@ Linia 4: / Linia 4: @@
 wtedy i tylko wtedy gdy dla pewnego k zachodzi
-</center>
+<center>
 <math> RightTest(v_1, v_2\ldots v_{k-2},\ v_{k-1}v_k lub Righttest(v_1, v_2\ldots v_{k-1},\ v_k) </math></center>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.