Zaawansowane algorytmy i struktury danych/Ćwiczenia 3

Zadanie 1

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