https://pl.spoj.com/problems/AL_08_04
Skrócony opis problemu:
Dla danego wyrazu $str$ o długości $n$ znajdź długość najdłuższego (niekoniecznie spójnego) palindromu, który zawiera.
Np. dla wyrazu "algoliga" odpowiedź to 5. Najdłuższe palindromy to bowiem: "algla", "alola", "agoga", "aglga" i "agiga" (wszystkie mają długość 5).
Rozwiązanie naiwne:
Można sprawdzić wszystkie podciągi danego wyrazu i sprawdzić dla każdego z nich czy jest palindromem i zapamiętać długość największego z nich.
Złożoność: $O(n \cdot 2^n)$, bo mamy $\sum_{i=2}^n \binom{n}{i} = 2^n-n-1$ podciągów (ciągi o długości 1 pomijamy, bo wiemy, że są palindromami), a dla każdego z nich sprawdzamy czy jest palindromem w liniowym czasie ($O(n)$).
Rozwiązanie naiwne nr 2:
Możemy użyć następującego wzoru rekurencyjnego:
$$out(a,b) = \begin{cases} 1 &\text{dla } a=b \vee \left(b=a+1 \wedge str[b] \neq str[a+1]\right) \\ 2 &\text{dla } b=a+1 \wedge str[b]=str[a+1] \\ 2+out(a+1,b-1) &\text{dla } str[a]=str[b] \\ \max(out(a,b-1),out(a+1,b)) &\text{w pozostałych przypadkach} \end{cases}$$
Funkcja $out(a,b)$ zwraca długość najdłuższego palindromu podciągu od indeksu $a$ do indeksu $b$.
Jeśli mamy długość podciągu równą 1 ($a=b$), to wynik to oczywiście 1. Jeśli mamy podciąg o długości 2, to wynik to 1 jeśli znaki się sobie nie równają, a 2 jeśli są równe. Dla większej ilości znaków mamy już rekurencję. Jeśli mamy podciąg, na którego końcach są te same znaki, do wynikiem będzie 2+długość najdłuższego palindromu z pominięciem tych znaków. Jeśli znaki na końcach są różne, to wybieramy maksimum z podciągu bez pierwszego znaku i podciągu bez ostatniego znaku.
Złożoność: $O(2^n)$, bo pesymistycznie rzecz biorąc będziemy w każdym wywołaniu wykonywać funkcję 2 razy, więc ilość wywołań funkcji rośnie wykładniczo.
Rozwiązanie sprytne:
Rozwiązanie to jest bardzo podobne do poprzedniego z jedną, małą zmianą. Mianowicie będziemy tablicować nasze wyniki. Jak bowiem wygląda zapytanie? Jest to pytanie o parę liczb. Każda z liczb jest z przedziału $\left<0;n-1\right>$ (jeśli indeksujemy od 0). Możemy więc w dwuwymiarowej tablicy zapisać sobie nasze wyniki, dzięki czemu będziemy obliczać wynik dla każdej pary tylko raz. W poprzednim rozwiązaniu mamy złożoność wykładniczą, ale przez to, że wiele wywołań się powtarza. Tablicowanie eliminuje ten problem.
Złożoność: $O(n^2)$, bo taka jest maksymalna liczba par indeksów.
Rozwiązanie sprytne nr 2:
Rozwiązanie to jest z kolei bardzo podobne do poprzedniego. Tutaj również będziemy tablicować wyniki. Jaka jest zatem różnica? Nie będziemy robić tego rekurencyjnie, ale iteracyjnie.
Spróbujmy zasymulować poprzedni algorytm dla $n=3$. Wywołujemy $out(0,2)$. Wchodzimy do ostatniego ifa i wywołujemy najpierw $out(0;1)$, dla którego zwracamy 1. Następnie wracamy się i wywołujemy $out(1,2)$ i tu zwracamy 2 (bo $str[1]=str[2]$). Następnie bierzemy maxa z tych 2 wyników i zwracamy jako ostateczny wynik.
Co tu widzimy? Otóż to, że najpierw potrzebujemy par o mniejszych odległościach między indeksami, żeby obliczyć te większe. Stwórzmy więc tablicę $tab$ i dla każdej pary indeksów $(i;i)$ dla $i \in \left<0;n-1\right>$ zapiszmy $tab[i][i]=1$. Następnie dla każdej pary $(i,i+1)$ dla $i \in \left<0;n-2\right>$ zróbmy $tab[i][i+1]=1$ jeśli $str[i] \neq str[i+1]$ i $tab[i][i+1]=2$ jeśli $str[i]=str[i+1]$. Na koniec przejdźmy wszystkie pozostałe pary i zastosujmy zamiast wywołań ww. wzoru rekurencyjnego odwołania się do komórek. Tak więc $out(a,b) = tab[a][b]$. Musimy jednak pamiętać, które z pozostałych par musimy obliczyć na początku. Do obliczenia $tab[i][j]$ może być potrzeba $tab[i+1][j-1]$ dla przedostatniego warunku oraz $tab[i][j-1]$ i $tab[i+1][j]$ dla ostatniego. Musimy więc zacząć od minimalnych $j$ i maksymalnych $i$.
Na koniec wypisujemy $tab[0][n-1]$.
Złożoność: $O(n^2)$, bo sprawdzamy każdą z $\frac{n(n+1)}{2}$ par $(i;j)$ dla $i \le j$. To rozwiązanie ma taką zaletę, że oprócz tego, że przechodzimy tylko [około] połowę macierzy, to jeszcze nie korzystamy z rekurencji, która spowalnia program, gdyż musi zapisywać na stosie wszystkie wywołania. Wadą tego rozwiązania jest obliczania wszystkich par, podczas gdy w poprzednim rozwiązaniu obliczaliśmy tylko te potrzebne.
Optymalizacja: Możemy zoptymalizować złożoność pamięciową. Obecnie wynosi ona również $O(n^2)$, jednak da się wykorzystać jedynie $O(n)$ pamięci. Wystarczy pamiętać tylko 2 wiersze. Do obliczenia wiersza $tab[i]$ potrzebujemy bowiem jedynie wiersza $tab[i+1]$. Możemy zatem w jednym wierszu przechowywać aktualny wynik i korzystać do jego obliczenia drugiego wiersza a potem używać ich na odwrót. Pomysł ten zdradził mi Maciej Boniecki.
Ostateczny algorytm:
int main() { int n, i, j; // n obliczamy sami char str[n]; // dane int tab[n][n]; for(i = 0; i < n; ++i) tab[i][i] = 1; for(i = 0; i < n-1; ++i) tab[i][i+1] = 1+(str[i] == str[i+1]); for(i = n-3; i >= 0; --i) // zaczynamy od 3 linii od końca, bo 2 ostatnie już uzupełniliśmy powyżej for(j = i+2; j < n; ++j) // tu tak samo - pomijamy 2 elementu już uzupełnione if(str[i] == str[j]) tab[i][j] = 2+tab[i+1][j-1]; else tab[i][j] = max(tab[i+1][j], tab[i][j-1]); print(tab[0][n-1]); }
Rozwiązanie szybkie nr 3:
Autorem tego rozwiązania jest Adam Bąk.
Można zauważyć, że rozwiązaniem tego zadania będzie znalezienie najdłuższego wspólnego podciągu wyrazu $str$ oraz jego odwrócenia.
Weżmy np. wyraz adambak. Wspak to kabmada. Obliczamy NWP (ang. LCS) z użyciem programowania dynamicznego (nawiasem mówiąc, poprzednie rozwiązanie też korzysta z programowania dynamicznego, gdyż korzystamy z mniejszych wyników, aby obliczyć większy) owych dwóch wyrazów i jest to "aba", "ama", "aaa" lub "ada". Wynik to zatem 3.
Tutaj znajdziecie porządny opis NWP wraz z przykładami, różnymi algorytmami, programami i ilustracjami. Ogólnie bardzo polecam tę stronę. Można się z niej wiele nauczyć. Są tam opisywane algorytmy jeszcze dokładniej niż tutaj, lecz tu skupiamy się na konkretnym zadaniu, a tam na konkretnym problemie / algorytmie / strukturze danych.
Zaletą tego algorytmu jest jego popularność - możemy więc na zawodach zakodzić to bez zastanawiania się nad poprawnością kodu (oczywiście mając pod ręką kod do obliczania NWP).
Dowód tego algorytmu możecie znaleźć w komentarzach.
Złożoność: $O(n^2)$, ze względu na złożoność obliczania NWP w czasie $O(nm)$, gdzie $m$ to długość drugiego ciągu. U nas $m=n$, jako że drugi ciąg to odwrócony ciąg pierwszy.
Brakuje mi dowodu, że ten ostatni algorytm działa.
OdpowiedzUsuńBardzo słusznie bo to nie jest oczywiste. Istotnie nie każdy NWP słów $w$ i $w^R$ (odwrócone) jest od razu NPP (najdłuższy podciąg palindromiczny) słowa $w$. Weźmy na przykład $w=ABCABCA$, wtedy NWP to na przykład $ACABA$, które to palindromem nie jest.
OdpowiedzUsuńTo może tak:
Prawdą jest, w sposób oczywisty, że każdy NPP słowa $w$ jest wspólnym podciągiem słów $w$ i $w^R$. To nam daje ograniczenie górne na długość NPP w postaci długości ich NWP. Niech $w=w_1w_2...w_n$, będzie słowem $n$ literowym. Weźmy dowolny NWP słów $w$ i $w^R$, który nie jest palindromem: $x=w_{i_1}w_{i_2}...w_{i_j}...w_{i_k}$ tak, że $w_{i_j}$ jest środkową literą $x$, czyli $j-1=k-j$ (dla uproszczenia $|x|\equiv_2 1$, dla parzystej długości zupełnie analogicznie). Skoro $x$ nie jest palindromem to: $s_1=w_{i_1}...w_{i_{j-1}}\neq w_{i_{k}}...w_{i_{j+1}}=s_2^R$. Zaznaczając wtedy $w_{i_j}$ w $w$ mamy: $w=r_1w_{i_j}r_2$ oraz $w^R=r_2^Rw_{i_j}r_1^R$. Teraz z $x\sqsubseteq w^R$ (jest podciągiem) widać, że $s_1\sqsubseteq r_2^R$, czyli też $s_1^R\sqsubseteq r_2$. No to w takim razie możemy zmodyfikować $x$ na słowo $x'=s_1w_{i_j}s_1^R$, gdzie $|x|=|x'|$, czyli algorytm można bez obaw stosować.
Moim zdaniem nie widać tak bardzo, że $s_1\subseteq r_2^R$. To co po cichu zakładasz, to że $w_{i_j}$ dopasuje się do tego samego wystąpienia tej litery w $w^E$.
OdpowiedzUsuńFaktycznie wygląda to bardzo źle. Nie udało się :-(
OdpowiedzUsuńRozwiązaniem by było znalezienie jak najmniejszego przedziału w słowie $w$ w który wpada ten znak przy dopasowaniu zarówno $x$ jak i $x^R$ do $w$, z czego by wynikało że możemy tak ten palindrom utworzyć. Ja niestety mogę pomarzyć o byciu tak pomysłowym, więc podaję link do (ładnego) dowodu który tak właśnie robi:
www.ece.umd.edu/~xiejw/files/palindrome.pdf
Ten fakt (jak widać) nie jest jednak taki prosty ;) Warto ten dowód dobrze przetrawić i zapamiętać!
OdpowiedzUsuń