Zaawansowane algorytmy i struktury danych/Ćwiczenia 3

From Studia Informatyczne


Zadanie 1

Udowodnij własność parzystych palstarów:

x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_0(i)

Rozwiązanie

.

Skorzystaj z kilku symetrii.

Zadanie 2

Udowodnij własność dowolnych palstarów:

x[i..n] \in PAL^* \ \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 PAL^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.