Algorytm Manachera

Problem

Zadanie polega na znalezieniu liczby wszystkich palindromów w zadanym łańcuchu znaków. Do rozwiązania tego zadania najlepiej na początku zastosować algorytm naiwny. Dla wygody przyjmijmy, że chodzi nam o palindromy nieparzystej długości. Naiwny algorytm polega na przechodzeniu przez zadany łańcuch znaków i dla każdej pozycji próbujemy znaleźć palindromy o coraz większej długości. Przy tego typu zadaniach bardzo często dodaje się wartowników na początku i końcu łańcucha znaków, aby uniknąć sprawdzanie, czy nie znaleźliśmy się poza łańcuchem. Załóżmy, że znaki # i & nie występują w zadanym łańcuchu i dodajemy je odpowiednio na początku i końcu łańcucha. Niech nasz początkowy ciąg wygląda następująco: #abbaaaabbbaababab&.

s = "#abbaaaabbbaababab&"

sum = 0
for i in 1...s.length-1
 sum += 1
 r = 1
 while s[i-r] == s[i+r]
  sum += 1
  r += 1
 end
end

p sum

Powyższy kod zlicza ilość palindromów o nieparzystej długości. Zaczynamy od pierwszego znaku po # i kończymy na ostatnim znaku przed &. Uważny czytelnik z pewnością spostrzeże, że możemy zacząć o jeden znak później i skończyć i jeden znak wcześniej inicjując sumę wartością 2. Ta kosmetyczna modyfikacja (pomijając kłopoty z łańcuchami krótszymi niż 2 znaki) nie zmienia faktu, że powyższy algorytm ma złożoność kwadratową od długości wejściowego łańcucha znaków.

Nomenklatura

Zanim przejdziemy do zaprezentowania szczegółów algorytmu Manachera, wprowadźmy pojęcie promienia palindromu. Promieniem palindromu będziemy oznaczać połowę jego długości w przypadku palindromów o długości parzystej. Dla palindromów o długości nieparzystej będzie to sufit z całkowitej długości palindromu podzielonej przez 2. Nie ma w tym niczego tajemniczego, ale żeby nie pozostawiać żadnych niejasności kilka przykładów: R("abba") = 2, R("abbabbabba") = 5, R("aba") = 2, R("abbabababba") = 6, R("a") = 1, R("") = 0.

Formalnie rzecz ujmując jeśli przez s^R oznaczymy łańcuch s czytany od końca, to palindromy parzyste będą miały postać ss^R zaś nieparzyste sws^R. Jeśli przez |s| oznaczymy długość łańcucha s to promień dla palindromów parzystym możemy przedstawić jako R(ss^R) = s, zaś dla nieparzystych przyjmie postać R(sws^R) = s (zakładając, że w jest dowolnym pojedynczym znakiem).

Liczenie promieni metodą naiwną

W wielu różnych opracowaniach algorytmu Manachera najczęściej omawia się ten algorytm na przykładzie liczenia ilości palindromów parzystych. My też poddamy się tej konwencji, z tym, że w pierwszym podejściu do liczenia promieni palindromów parzystych wykorzystamy ponownie algorytm naiwny. Zanim jednak to zrobimy zwróćmy uwagę na jeden techniczny szczegół. W tym celu posłużymy się rysunkiem.

Powyższy rysunek przedstawia obliczone długości promieni dla łańcucha znaków #abbaaaabbbaababab&. Długości promienie znajdują tuż powyżej łańcucha znaków. Warto zwrócić uwagę, że komórki powyżej są odrobinę przesunięte w stosunku do komórek poniżej. Jest to celowy zabieg, aby lepiej zobrazować relację pomiędzy poszczególnymi komórkami zawierającymi znaki wejściowego łańcucha a długością promienia palindromu.
Widzimy, że promień w indeksie 0 został wyliczony na ze znaków łańcucha znajdujących się na pozycjach 0 i 1. Promień ten wynosi 0. Promień długości 2 znajduje się w tablicy pod indeksem 2 (oraz pod indeksem 11). Został on wyliczony na podstawie indeksów 1, 2, 3, 4 wejściowego łańcucha znaków.
Ogólnie rzecz ujmując chcą obliczyć promień na pozycji k sprawdzamy, czy łańcuchu znaki na pozycjach k i k + 1 są identyczne. Idąc dalej tym tropem będziemy sprawdzać kolejne znaki na lewo i prawo od środka palindromu.
Jesteśmy już gotowi, aby napisać kod obliczający długości palindromów parzystych.

s = "#abbaaaabbbaababab&"

r = []
for i in 0...s.length-1
 k = 0
 while s[i-k] == s[i+1+k]
  k += 1
 end
 r << k
end

p r

Ważne obserwacje

Powyższy algorytm ma złożoność kwadratową. Jest tak ponieważ wykonuje on pewne obliczenia nadmiarowo nie korzystając z własności palindromów. Okazuje się, że powyższy naiwny algorytm można znacząco przyspieszyć. W tym celu przeanalizujmy kilka przykładowych wejściowych łańcuchów znaków.

Obserwacja nr 1

Załóżmy, że obliczyliśmy wszystkie długości promieni na pozycjach od 0 do 7. Czy możemy coś wywnioskować o długości promieni na dalszych pozycjach na podstawie wcześniejszych obliczeń? Najdłuższym dotychczas znalezionym palindromem jest palindrom o promieniu 6 (babbaaaabbab). Jego lewym kraniec zaczyna się wejściowym łańcuchu znaków od pozycji 2, prawy zaś kraniec kończy się w łańcuchu na pozycji 13. Zauważmy, że na pozycjach od 3 do 6 oraz od 6 do 7 znajdują się palindomy. Palindromy te mają tę właściwość iż ich lewe końce nie wystają poza lewy koniec większego palindromu, w którym się znajdują. Postarajmy się to pokazać na rysunku.

Palindromy zostały zaznaczone trzema różnymi kolorami. Palindromy obrysowane kolorami zielonym i fioletowym mieszczą się w całości wewnątrz większego palindromu obrysowanego kolorem czerwonym. Skoro tak, to mając na uwadze symetryczność palindromu czerwonego (w ogólności wszystkich palindromów) wnosimy, że możemy skopiować pewne wartości obliczone dla jego lewej połowy do jego prawej połowy. W naszym przypadku zauważamy, że promień o długości 1 na pozycji 6 może być skopiowany na pozycję 8 (oś najdłuższego palindromu znajduje się na pozycji 7). Analogicznie możemy postąpić z promieniem na pozycji 4 kopiując jego długość na pozycję 10. A co z pozostałymi "palindromami" o promieniu długości 0? Ich długości także śmiało kopiujemy. Jedyny promień który nie może być bezkrytycznie skopiowany to promień na pozycji 1. Jest tak dlatego, że na pozycji 13 tak naprawdę znajduję się palindrom o promieniu 2. Tak naprawdę to możemy skopiować promień z pozycji 1 na pozycję 13 i spróbować go powiększyć, ale nie uprzedzajmy faktów. Najważniejszą rzeczą jaką musimy zapamiętać z tej obserwacji jest to, że umiemy sobie radzić z palindromami, które znajdują się całkowicie wewnątrz większego palindromu w taki sposób, aby ich lewe krawędzie nie nachodziły na siebie. Tymczasem druga ważna obserwacja.

Obserwacja nr 2

Jak już stwierdziliśmy podczas pierwszej obserwacji są sytuacje, kiedy trzeba zrobić coś więcej niż skopiować promień z lewej części palindromu do prawej części. Okazuje się, że dzieje się to wtedy, kiedy skrajny lewy koniec wewnętrznego palindromu pokrywa się ze skrajnym lewym końcem zewnętrznego palindromu. Inna sprawa, że przypadek podany w obserwacji nr 1 jest pod tym względem zdegenerowany ponieważ długość promienia wewnętrznego palindromu wynosi 0. Nie przeszkadza to wcale temu, że lewy koniec tego "palindromu" kończy się na pozycji 1 (w tym samym miejscu co się zaczyna), czyli dokładnie w tym samym miejscu co palindrom na pozycji 7 o promieniu 6. Przyjrzyjmy się jednak przypadkowi, który zobrazuje nam problem pełniej.

Rzecz, na którą warto tutaj zwrócić uwagę to to, że palindrom na pozycji 3 o promieniu 2 ma swój lewy koniec w tym samym miejscu co większy palindrom z pozycji 6 o promieniu 5 (3-2 = 6-5). Czy w związku z tym promień z pozycji 3 jest równy promieniowi na pozycji 9. Nie. Na pozycji 9 znajduje się palindrom o promieniu 4. Czyli w tym przypadku te dwa promienie nie są sobie równe. Rodzi się pytanie czy takich wyjątkowych sytuacji nie będzie więcej i czy nie skomplikuje się przez to nasz algorytm? Okazuje się, że nie. To jest jedyna taka wyjątkowa sytuacja. Żeby się o tym przekonać przejdźmy czym prędzej do obserwacji nr 3.

Obserwacja nr 3

Skoro analizowaliśmy już przypadki takie, że koniec wewnętrznego palindrom, albo mieści się wewnątrz albo kończy się w tym samym miejscu co zewnętrznym palindrom to pozostaje jeszcze tylko jedna możliwość. Koniec palindromu wewnętrznego wystaje poza obręb zewnętrznego palindromu. Okazuje się, że jest to dosyć podobny przypadek do tego z obserwacji nr 1, choć na pierwszy rzut oka nie jest to oczywiste. Poniższy rysunek będzie tutaj bardzo pomocny.

W pewnym sensie jest to przypadek najtrudniejszy. Przyjrzyjmy się temu rysunkowi i zastanówmy się co już wynika z obliczonych promieni palindromów. Palindrom na pozycji 5 posiada promień długości 3 a to oznacza na pewno, że nie można go już poszerzyć i co za tym idzie w wejściowym napisie znaki na pozycjach 2 i 9 muszą się różnić. Gdyby były takie same to promień z pozycji 5 można byłoby zwiększyć. To bezsprzeczny fakt. Teraz niech naszą uwagę przykuje krótszy palindrom na pozycji 3 o promieniu 2. Palindrom ten powinien mieć swój bliźniaczy odpowiednik na pozycji 7. Jednakże na pozycji 7 znajduje się palindrom o promieniu zaledwie 1. Dlaczego tak się dzieje? Otóż, żeby palindrom na pozycji 7 miał długość 2 to znaki w wejściowym napisie na pozycjach 6 i 9 powinny być sobie równe. Odpowiadają one odpowiednio pozycjom 5 i 2 z palindromu o środku na pozycji 3. Czyli znaki w napisie wejściowym na pozycjach 2,5,6 i 9 powinny być sobie równe. Tak jednak nie jest bo na pozycji 9 jest na pewno inny znak niż na pozycji 2 poniewać palindrom na pozycji 5 ma promień dokładnie długości 3. W związku z powyższym jeśli jakiś palindrom wystaje poza lewą krawedź zewnętrznego palindromu, to jego odpowiednik po prawej stronie nie bedzie miał takiego samego promienia. Jego promień będzie wynosił tylko tyle ile jest w stanie zmieścić się w obrębie tego większego palindromu Jest to bardzo ważna obserwacja dlatego czytelnik powinien się upewnić, że dobrze ją rozumie zanim przejdzie do dalszej lektury.

Algorytm

Postaramy się pokazać algorytm budując go od podstaw. To co jest pewne to to, że musimy w jakiś sposób przechodzić kolejne znaki napisu wejściowego (jak się zaraz okaże nie musi tego robić znak po znaku). Nasz wstępny szkielet algorytmu wygląda następująco:

s = "#abbaaaabbbaababab&"

r = Array.new(s.length-1, 0) # tablica z promieniami palindromów
i = 0                        # indeks aktualnego obliczanego promienia
while i < r.length
 # znajdujemy promień dla aktualnego indeksu
 # ...

 # kopiujemy informacje o promieniach z lewej strony
 # palindromu na prawą
 # ...

 # zwiększamy indeks
 i += 1
end

p r

Oczywiście taki program nie wypisze na razie nic ciekawego, ale cierpliwości. Pierwszym krokiem będzie poszerzanie promieni. Początkowo długości promieni będą wynosić 0, ale z czasem nauczymy się jak można je zwiększać.

s = "#abbaaaabbbaababab&"

r = Array.new(s.length-1, 0) # tablica z promieniami palindromów
i = 0                        # indeks aktualnego obliczanego promienia
while i < r.length
 # znajdujemy promień dla aktualnego indeksu
 while (s[i - r[i]] == s[i + r[i] + 1])
  r[i] += 1;
 end

 # kopiujemy informacje o promieniach z lewej strony
 # palindromu na prawą
 # ...

 # zwiększamy indeks
 i += 1
end

p r

Powyższy kod to nic innego jak odrobinę zmodyfikowany (zamiast pętli for jest while) naiwny algorytm liczenia promieni. Nie wykorzystuje on jeszcze ukrytej mocy leżącej unikaniu wykonanych już wyliczeń. Następne ulepszenie algorytmu będzie to czynić.

s = "#abbaaaabbbaababab&"

r = Array.new(s.length-1, 0) # tablica z promieniami palindromów
i = 0                        # indeks aktualnego obliczanego promienia
while i < r.length
 # znajdujemy promień dla aktualnego indeksu
 while s[i - r[i]] == s[i + r[i] + 1]
  r[i] += 1
 end

 # kopiujemy informacje o promieniach z lewej strony
 # palindromu na prawą
 # sprawdzamy promienie z lewej strony od 1 do r[i]
 for k in 1..r[i]
  if r[i - k] < r[i] - k    # obserwacja 1
   r[i + k] = r[i - k]
  elsif r[i - k] > r[i] - k # obserwacja 3
   r[i + k] = r[i] - k
  else
   r[i + k] = r[i - k]   # obserwacja 2, ta linia lub ta poniżej
   #r[i + k] = r[i] - k  # promień może się zwiększyć 
  end
 end

 # zwiększamy indeks
 i += 1
end

p r

Algorytm się trochę skomplikował. Zaraz postaramy się go uprościć. Jak to działa? Zakładamy, że obliczyliśmy jakiś promień. Teraz analizujemy lewą połówkę tego palindoromu przechodząc przez kolejne elementy znajdujące się w obrębie tego palindromu (od środka palindromu na zewnątrz). W każdym kroku analizujemy, z którą obserwacją mamy do czynienia (mamy 3 możliwości). Aktualizujemy wartości promieni po prawej stronie palindromu. Zauważmy, że dla obserwacji 1 i 3 wartość wyznaczonego promienia nie ulegnie zmianie. Jak będziemy przechodzić przez te elementy w głównej pętli i próbować zwiększyć rozmiar promienia to ta próba będzie nieudana i przejdziemy od razu do kolejnego elementu. Z kolei jeśli będzie zachodziła obserwacja 2 to rozmiar promienia może ulec zwiększeniu. Ale w tym przypadku będziemy często startowali już jakimś promieniem większym od 0. Druga obserwacja sprawia, że możemy trochę uprościć powyższy kod. Zauważmy, że zawsze kiedy porównujemy r[i - k] oraz r[i] - k to pod r[i + k] podstawiamy to co jest mniejsze z tych dwóch wartości. Jeśli jest obserwacja 2 to nie ma to znaczenia ponieważ obie wartości są równe. Pozwala nam to uprościć kod w następujący sposób.

s = "#abbaaaabbbaababab&"

r = Array.new(s.length-1, 0) # tablica z promieniami palindromów
i = 0                        # indeks aktualnego obliczanego promienia
while i < r.length
 # znajdujemy promień dla aktualnego indeksu
 while s[i - r[i]] == s[i + r[i] + 1]
  r[i] += 1
 end

 # kopiujemy informacje o promieniach z lewej strony
 # palindromu na prawą
 # sprawdzamy promienie z lewej strony od 1 do r[i]
 for k in 1..r[i]
  r[i + k] = [r[i - k], r[i] - k].min
 end

 # zwiększamy indeks
 i += 1
end

p r