Zaawansowane algorytmy i struktury danych/Ćwiczenia 3

Zadanie 1

Udwodnij, że jeśli $LZ(x)=(v_1,v_2,\dots ,v_m)$ to x zawiera powtórzenie uu wtedy i tylko wtedy gdy dla pewnego k zachodzi

$RightTest(v_1,v_2\dots v_{k-2},v_{k-1}{v}_{k}lubRighttest(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.

Zadanie 2

Oblicz faktoryzację LZ(x) w czasei liniowym.

Rozwiązanie

.

Skorzystaj z drzewa sufiksowego, z dodatkową informacja w węzłach.

Zadanie 3

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|\le 2n$

Zadanie 4

Udowodnij własność parzystych palstarów:

$x[i..n]\in PA{L}_0^{*}\Rightarrow pars{e}_0(i)=firs{t}_0(i)$

Rozwiązanie

.

Skorzystaj z kilku symetrii.

Zadanie 5

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

$x[i..n]\in PA{L}^{*}\Rightarrow parse(i)\in \{first(i),2\cdot first(i)+1,2\cdot first(i)-1\}$

Rozwiązanie

. Skorzystaj z kilku symetrii

Zadanie 6

Udowodnij, że jeśli $x\in PA{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

. Skorzystaj z symetrii.