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

Wersja z 12:27, 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

Udowodnij, że jeśli $x \in P A L^{2}$

to x=uv, dla pewnych <mtah> u,v \in PAL </math> gdzie u jest najdłuższym palindromem będącym prefiksem x lub v

jest najdłuższym palindromem będącym sufiksem x.

Rozwiązanie

@@ Linia 1: / Linia 1: @@
 ==Zadanie 1==
 Udwodnij, że jeśli <math> LZ(x)\ =\ (v_{1},v_{2},\dots ,v_{m})</math> to x zawiera powtórzenie uu
@@ Linia 53: / Linia 52: @@
 Skorzystaj z kilku symetrii</div>
+</div>
+==Zadanie 6==
+Udowodnij,  że jeśli <math> x \in PAL^2</math>
+ to x=uv, dla pewnych <mtah> u,v \in PAL </math> gdzie u jest najdłuższym palindromem będącym prefiksem x lub v
+jest najdłuższym palindromem będącym sufiksem x.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
+Skorzystaj z symetrii. </div>
 </div>