CERC 2010: Szkice rozwiązań

28.11.2010

C: Casting Spells

Treść (pdf) | wyślij rozwiązanie.

W tym zadaniu celem jest znalezienie najdłuższego podsłowa w postaci wwRwwR lub — innymi słowy — najdłuższego parzystego palindromu złożonego z dwóch mniejszych parzystych palindromów. Warto zatem zacząć od stworzenia zwięzłego opisu wszystkich parzystych palindromów. Jeśli dane słowo oznaczymy przez s[1..n], to dla każdego i=1,2,...,n, chcemy obliczyć największe k, takie że s[i]=s[i-1], s[i+1]=s[i-2], ..., s[i+k]=s[i-1-k]. Wielkość k=r(i) nazywamy palindromicznym promieniem w miejscu i. Jak wiadomo, promienie we wszystkich miejscach można wyznaczyć za pomocą algorytmu Manachera.

Po wyliczeniu wszystkich promieni r(i) pozostaje się nam zmierzyć z następującym zadaniem: dla każdego i=1,2,...,n wyznacz największe k ≤ r(i) takie, że istnieje j z przedziału [i-k/2,i-1], dla którego j+r(j)≥ i. Liczba i odpowiada centrum potencjalnego palindromu w postaci wwRwwR, a i-j jest długością słowa w. Zadanie to można rozwiązać przechodząc po słowie od lewej do prawej strony i przechowując wszystkie potencjalne indeksy j uporządkowane względem wartości j+r(j). Indeksy te należy przechowywać w strukturze umożliwiającej szybkie dodawanie, usuwanie i pytanie o następnika. Aby przetworzyć dany indeks i, najpierw wstawiamy i-1 do struktury, następnie usuwamy wszystkie indeksy j dla których j+r(j)<i i znajdujemy następnik i-k/2 (jeśli istnieje). Ten następnik odpowiada najdłuższemu słowu w dla bieżącego miejsca i. Implementacja struktury za pomocą zbalansowanego drzewa binarnego umożliwia uzyskanie czasu O(n log n).

Informacje dodatkowe

Jeśli nie znamy algorytmu Manachera, nie należy rozpaczać. Akceptowane rozwiązanie (działające w czasie O(n log n)), a więc nie pogarszające asymptotycznej złożoności wzorcowego rozwiązania, przedstawione przez wiele drużyn, wykorzystywało binarne przeszukiwanie. Dla każdego i, sprawdzenie czy dane k jest dobrym palindromicznym promieniem można wykonać wykorzystując haszowanie do sprawdzenia równości dwóch fragmentów s w stałym czasie.

Jeśli jednak zastosujemy algorytm Manachera, aby wykonać preprocessing w czasie liniowym, okazuje się, że możliwe jest poprawienie czasu całego algorytmu z wykorzystaniem algorytmu union-find. Szczegóły pozostawiamy czytelnikowi jako interesujące ćwiczenie.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com