Zaawansowane algorytmy i struktury danych/Ćwiczenia 3

Zadanie 1

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 2

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 3

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.