Mamy pewne słowo s[1..n], gdzie chcemy dla każdego i, takie że 1 ≤ i ≤ n wyznaczyć R[i], będące promieniem największego palindromu parzystego który ma środek w i. Dokładniej R[i] to taka największa liczba, że s[i-R[i] .. i+R[i]+1] jest palindromem parzystej długości.

Algorytm działa tak, wyliczamy pierwszą wartość funkcji R, a potem w czasie stałym znajdujemy wartości R[i+k] dla k, takiego że R[i] ≤ k ≤ R[i+k], czyli takie które mieszą się pod tzw. "parasolem" palindromu o promieniu R[i].

Wykorzystujemy niezwykłą obserwację: jeżeli k jest takie, jak wyżej zostało opisane i R[i-k] różne od R[i]-k, to R[i+k] = min(R[i-k], R[i]-k).

Skąd to się w ogóle bierze? Pomyślała większość czytelników. Ano dowód nie jest zbyt przyjemy nawet jeżeli użyje obrazków, osobą którym nie jest to do szczęścia potrzebne mogą go pominąć tak czy siak, poniżej wykonam zobrazowany dowód.

Mamy dwa przypadki!

1. R[i-k] < R[i]-k, to oznacza że cały palindrom z pozycji R[i-k] znajduję się pod "parasolem" palindromu R[i], dzięki właściwością palindromu R[i], możemy powiedzieć że to przenosi się na pozycje R[i+k]. Dosyć teorii czas na obrazek!
   
   
   Niebieski R[i-k]
   Czerwony R[i]
   Zielony R[i+k]
   
   Wszystko jasne, jedziemy dalej ;)
   
   
2. Jeżeli R[i-k] > R[i]-k, to z kolei palindrom R[i-k] wystaje poza daszek palindromu R[i]. Ponownie wykorzystując właściwości palindromu R[i], mamy, że R[i+k] ≥ R[i]-k.
   Jednakże uwaga! Czemu to nie może być większe?
   Otóż wiemy że litera s[i-R[i-k]-1] jest różna od litery s[i+R[i]+k], wiemy ta stąd iż jeżeliby były one sobie równe to cały palindrom by się powiększył!
   
   
   Innymi słowy daszek z pozycji R[i]-k nie da się rozszerzyć czyli R[i+k]=R[i]-k.
   
   

To kończy dowód, kilka rzeczy w tym dowodzie uznałem za intuicyjne, jednakże mam nadzieję, że udało mi się wszystko w miarę możliwości wytłumaczyć.

Jako zabawę na zrozumienie tego algorytmu polecam przerobić go tak aby działał dla palindromów Nieparzystych!