Poniższy algorytm dla zadanego słowa \(\displaystyle{ w = w_1w_2 \ldots w_n}\) znajduje najdłuższym palindrom będący jego podsłowem (np. dla słowa skok algorytm zwróci kok)
Kod: Zaznacz cały
Maxpali(w)
i := 1
j := n
while (i<j) and (wi =wj) do
i := i +1
j := j -1
if i >= j
then return w
else
u := Maxpali(w1…wn-1)
v := Maxpali(w2…wn)
if |u| > |v|
then return u
else
return v
Moje przemyślenia:
- linie 2,3,7 wykonują się zawsze raz
- linie od 8 do 15 wykonują się 0 do 1 razy w zależności od warunku
- główne operacje pod kątem złożoności dla tego algorytmu zawierają się w pętli while
- warunki w pętli sprawdzane są minimum 1 raz, maksymalnie n (np. dla słowa "aa")
- operacje wewnątrz pętli wykonują się n-1 razy
Nie wiem, czy moje rozumowanie jest poprawne, niestety chyba nie, ponieważ nie potrafię do niczego dojść. Nie wiem co się robi w takiej sytuacji z operatorem logicznym oraz z rekurencją.
Bardzo proszę o jakąkolwiek pomoc,