Tekst źródłowy strony Zaawansowane algorytmy i struktury danych/Ćwiczenia 3




== Zadanie 1==

Udowodnij własność parzystych palstarów: 

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

<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.

Skorzystaj z kilku symetrii.
</div>
</div>

== Zadanie 2 ==

Udowodnij własność dowolnych palstarów:

<math>x[i..n] \in PAL^* \ \Rightarrow\ parse(i)\in \{first(i),\ 2\cdot first(i)+1,\ 2\cdot first(i)-1\}</math>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.

Skorzystaj z kilku symetrii</div>
</div>



==Zadanie 3==
Udowodnij,  że jeśli <math>x \in PAL^2</math> 
to <math>x=uv</math> dla pewnych <mtah> u,v \in PAL</math>, gdzie <math>u</math> jest najdłuższym palindromem będącym prefiksem <math>x</math> lub <math>v</math> 
jest najdłuższym palindromem będącym sufiksem <math>x</math>.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.

Skorzystaj z symetrii. </div>
</div>