algorytm.org

Algorytm Manachera

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Manachera
Ocena użytkowników:***** / 166
SłabyŚwietny 
Wpisany przez Emil Hotkowski, 01 lutego 2012 21:07

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!

    Algorytm Manachera - dowód - przypadek 1

    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ł!

    Algorytm Manachera - dowód - przypadek 2

    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!
Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Emil HotkowskiC/C++
.cpp
.cpp
***** / 8
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 18:27
Dodaj komentarz