Postanowiłem wypełnić tę, jakby to powiedział prof. Choiński, "wpieprzającą ludzi" lukę tym, co znajduje się w moim zeszycie. Nie jest tego wiele, ale może jakoś uda się zrekonstruować algorytm Manachera.
Co to jest palindrom, każdy wie. Chcemy znaleźć wszystkie palindromy, będące podsłowami danego słowa (T). Przy czym pozwolę tu sobie na dwa małe uproszczenia:
- Rozważać będziemy tylko palindromy o nieparzystych długościach
- Rozważać będziemy tylko palindromy maksymalne, tj. takie, których się nie da więcej poszerzyć. Dla fragmentu tekstu "gacbcah" nasz algorytm znajdzie tylko palindrom "acbca" i powie, że jego środek jest w b.
ad 1. -> Tu w sukurs przychodzi nam magiczny znak "#", albo jakikolwiek inny, który w tekście na pewno nie wystąpi. Wstawiamy go co drugą literkę. Załóżmy, że w początkowym słowie mieliśmy palindrom o długości parzystej, którego środek wypadał pomiędzy literkami p i q. Jeżeli jego długość wynosiła 2k, to oznacza, że wsadziliśmy pomiędzy jego literki 2k-1 znaków "#", w szczególności jeden na środku, pomiędzy literkami p i q. Długość tego palindromu wynosi 4k-1, co jest nieparzyste, a że to jest dalej palindrom, to chyba widać: idąc od "#" na środku mamy ciąg #-litera-#-litera… i w lewo …-litera-#-litera-#. A więc każdemu "#" na prawo od środka odpowiada "#" na lewo od środka, oddalony od środka o tyleż samo. Reasumując, po takiej operacji nasz uproszczony algorytm wykryje palindromy o długościach (pierwotnie) parzystych, musimy tylko pamiętać, żeby przy ich wypisywaniu pomijać znaczki "#".
ad 2. -> Ten problem chyba każdy umie rozwiązać ;)
No więc do rzeczy. Nasz algorytm policzy tablicę P[], zdefiniowaną jako:
P[i] -> najdłuższy palindrom o środku w i-tym miejscu T (tzw. promień palindromiczny)
Czyli formalnie rzecz biorąc:
(oczywiście przy odpowiednich założeniach, tzn. że wszystkie indeksy są nieujemne i P[0]=#).
Ponadto, nasz algorytm używać będzie jeszcze trzech zmiennych:
j - indeks środka palindromu, który obecnie sięga najdalej w prawo (niekoniecznie najdłuższego!)
p - indeks literki, którą aktualnie rozważamy
q - indeks literki odpowiadającej T[p] w palindromie o środku w T[j], jeżeli takowa istnieje ( wtedy q=j-(p-j)=2j-p (*)).
No więc załóżmy, że mamy już policzone P[1…(p-1)]. Mamy dwa przypadki:
a) $P[j]+j<p$ (rozważana literka nie znajduje się w żadnym ze znalezionych palindromów)
Wtedy liczymy P[p] naiwnie porównując ze sobą literki z prawej i lewej strony p, dopóki nie napotkamy na parę różniących się literek.
b) $P[j]+j \geqslant p$ (rozważana literka należy do palindromu o środku w T[j]).
Wtedy na pewno istnieje q. Co więcej, q<p (gdyż j<p, a q znajduje się po drugiej stronie j niż p). Mamy więc już policzone P[q]. Rozważmy więc trzy przypadki:
1.$q-P[q]>j-P[j]$(palindrom o środku w q w całości zawiera się w palindromie o środku w j).
Wtedy palindrom o środku w p też będzie się w całości zawierał w palindromie o środku w j, gdyż wszystkie literki z palindromu o środku w q, będące przed q, powtórzą się po p (istotnie:
i analogicznie $T[q+k]=T[p-k]$). Tak samo dowodzimy, że $T[p-P[q]-1] \neq T[p+P[q]+1]$, co możemy zrobić, gdyż
(3)(i analogicznie $q-P[q]-1 \geqslant j-P[j]$, a więc niepasujące literki jeszcze mieszczą się w palindromie. Gdyby się nie mieściły, wtedy byłaby nadzieja na to, że tam zachodzi równość, co stanowi przypadek trzeci. Ale póki co w zasadzie nie ma o czym gadać, przepisujemy, że P[p]=P[q] i idziemy dalej.
2. $q-P[q]<j-P[j]$ (palindrom o środku w q wystaje poza palindrom o środku w j).
Wtedy wszystkie literki na lewo od q, mieszczące się w palindromie o środku w j, powtórzą się też na prawo od p, a że należą one do palindromu o środku w q, to powtórzą się też na lewo od p (wszystkie dowody takich twierdzeń są takie same (lub analogiczne) jak w przypadku pierwszym, a więc dość trywialne, nie chce mi się ich przepisywać) i stąd $P[p] \leqslant q-(j-P[j])=j-p+P[j]=j+P[j]-p$. Pytanie, co z literką o indeksie j+P[j]+1=p+(j+P[j]+1-p)=p+(P[j]+1+q-j). Chcielibyśmy, żeby była ona taka sama jak ta o indeksie p-(P[j]+1+q-j), wtedy palindrom o środku w p byłby o 1 dłuższy. Ale przecież ta literka znajduje się wewnątrz palindromu o środku w j, a więc (z (2)) mamy, że jest ona taka sama jak q+(P[j]+1+q-j), a jako że $P[j]+1+q-j \leqslant P[j]+P[q]-P[j]=P[q]$ ( z przyjętego założenia), to ta literka jest taka sama jak T[q-(P[j]+1+q-j)]=T[j-P[j]-1]. A więc mielibyśmy T[j-(P[j]+1)]=T[j+P[j]+1], czyli podsłowo o środku w j byłoby palindromem o promieniu co najmniej P[j]+1, stąd oczywiście mamy sprzeczność. A więc P[p]=j+P[j]-p i ani kroku dalej.
3. $q-P[q]<j-P[j]$ (palindrom o środku w q zaczyna się dokładnie wtedy, kiedy zaczyna się palindrom o środku w j). Wtedy, podobnie jak w przypadku drugim, na pewno wszystkie literki na lewo od q, mieszczące się w palindromie o środku w j, powtórzą się na prawo od p, i analogicznie jak tam otrzymujemy $P[p] \leqslant j+P[j]-p$. Tutaj jednak obostrzenia na P[j]+j+1 nie mamy, gdyż nie trzymają nas "wystające elementy" palindromu o środku w q. Dlatego… sprawdzamy naiwnie od T[j+P[j]].
Oczywiście powyższe, matematyczne tłumaczenie jest paskudnie zawiłe. Dlatego może pomoże w jego zrozumieniu poniższy rysunek:
Przypadek pierwszy: fakt, że litery a i b są różne, który blokuje rozszerzenie się palindromu czerwonego, blokuje też rozszerzenie się palindromu niebieskiego.
Przypadek drugi: a nie może być równe b, gdyż w przeciwnym wypadku czarny palindrom poszerzyłby się. Niebieski musi się więc skończyć razem z czarnym…
Przypadek trzeci: nie wiemy, co jest pod znakiem zapytania. Na pewno nie b, ale całkiem możliwe, że c. Trzeba to sprawdzić! ;)
Napiszmy pseudokod:
P[1]=0 //istotnie, P[0]!=P[2], bo P[0] po prostu nie istnieje j=1 for p=1 to |T| //przypadek a: if P[j]+j<p i=0 while T[p+i]=T[p-i] && p-i>0 //patrzymy też, czy nie wyjechaliśmy poza tablicę i++ P[p]=i //przypadek b: if P[j]+j>=p q=2*j-p //przypadek 1: if q-P[q]>j-P[j] P[p]=P[q] //przypadek 2: if q-P[q]<j-P[j] P[p]=j+P[j]-p //przypadek 3: if q-P[q]=j-P[j] i=j+P[j]-p while T[p+i]=T[p-i] && p-i>0 i++ P[p]=i //teraz trzeba sprawdzić, czy przypadkiem nie należy aktualizować j: if p+P[p]>j+P[j] j=p
Oczywiście, jeżelibyśmy chcieli wypisać wszystkie palindromy, to skwadraciłoby się na pewno (weźmy choćby tekst "aaaaaaaa"). Zastanówmy się jednak, jaka jest złożoność samego algorytmu Manachera, którego pseudokod widnieje powyżej:
Przypadki b-1 i b-2 działają w czasie stałym. Przypadki a i b-3 przesuwają j o tyle do przodu, ile wynosi liczba iteracji pętli while. Oczywiście nie mogą go przesunąć dalej niż |T|. Dlatego też te przypadki wykonają w sumie niewięcej operacji niż O(|T|). Przypadki b-1 i b-2 mogą być również maksymalnie O(|T|) razy wywoływane, gdyż pętla for wykona |T| przebiegów. A więc złożoność algorytmu Manachera wynosi O(|T|), a nawet $\Theta (|T|)$.
Powodzenia na sprawdzianie!
