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, $v_k$ nie występowałoby w faktoryzacji.

Zadanie 2

Oblicz faktoryzację LZ(x) w czasie liniowym.

Rozwiązanie

.

Skorzystaj z drzewa sufiksowego z dodatkową informacją w węzłach.

Zadanie 3

Udowodnij, że algorytm Szukanie-Powtórzeń dział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

Udowodnij 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.