ASD Ćwiczenia 13

Zadanie 1

Słowem pokrywającym tekst x taki tekst y, którego wystąpienia w x pokrywają cały tekst x. Na przykład aba pokrywa ababaaba, natomiast nie pokrywa tekstu abaaababa. Obliczyć długość najkrótszego słowa pkrywającego dany tekst x.

Rozwiązanie

Niech $S[i]$ będzie rozmiarem minimalnego pokrywajćego słowa dla prefiksu $x[1..i]$. Algorytm wykorzystuje następujący fakt: \ $S[i]=i\text{<mrow data-mjx-texclass="ORD">lub</mrow>}S[i]=S[P[i]].$ \ Następujący algorytm liczy długość minimalnego słowa pokrywającego tekstu x. Liczymy wartości $S[i]$ najmniejszej długości minimalnego słowa pokrywającego $x[1\dots i]$ dla każdego $1\le i\le n$. W $i$-tej iteracji algorytm pamięta jaki jest ``znany zakres każdego minimalnego słowa pokrywającego.

Rysunek 3: $i$-ta iteracja algorytmu, dla $i=15$, oraz słowa $x=abaabababaababa\dots$. Tuż przed rozpoczęciem tej iteracji mamy $P[i]=8$, $q=S[8]=3$, $Zakres[3]=13$. Po zakończeniu $i$-tej iteracji

mamy $S[15]=3,Zakres[3]=15$, ponieważ $i-Zakres[3]\le q$.

Algorytm Rozmiar-Minimalnego-Pokrycia

---

for $i:=2$ to $n$ do
   $Zakres[i]=i,S[i]=i$

for $i:=2$ to $n$ do
   if $P[i]>0$ oraz $i-Zakres[S[P[i]]\le S[P[i]]$ then
      $S[i]:=S[P[i]]$; $Zakres[S[P[i]]:=i$;

return $S[n]$;

Zadanie 2

Udowodnić, że w wersji on-line algorytmu KMP mamy $delay=O(logm)$

Rozwiązanie

Wystarczy wykazać, że

$P^{\prime }[i]=j,P^{\prime }[j]=k>0\Rightarrow i\ge k+j$

Fakt ten wynika z lematu o okresowości i z definicji tablicy P'.

Zadanie 3

Udowdnij poprawność algorytmy na cykliczną równoważność słów.

Rozwiązanie

Zdefiniujmy:

$D(u)=\{k:1\le k\le n$ oraz $u^{(k)}>w^{(j)}$ dla pewnego $j\}$,
$D(w)=\{k:1\le k\le n$ oraz $w^{(k)}>u^{(j)}$ dla pewnego $j\}$.

Skorzystamy z prostego faktu: Jeśli $D(u)=[1..n]$ lub $D(w)=[1..n]$, to $u,w$ nie są równoważne.

Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:

$D(w)\supseteq [1..i]$\ oraz \ $D(u)\supseteq [1..j]$.