15280. Szpieg u bram wioski [AL_08_04]

Zadanie:
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.