Choose jour language!

---

|

DP: Najduži zajednički podniz (LCS)

U ovoj lekciji upoznaćemo se sa problemom Najdužeg zajedničkog podniza (Longest Common Subsequence – LCS), koji je klasičan problem iz oblasti dinamičkog programiranja. Naučićemo kako da definišemo stanje, postavimo DP tabelu i analiziramo rešenje.

1. Opis problema

Dat su dva niza ili stringa X[1..n] i Y[1..m]. Cilj je pronaći najduži podniz koji se pojavljuje u oba niza. Podniz ne mora biti kontinualan.

Primer:

X = "AGGTAB"
Y = "GXTXAYB"
Najduži zajednički podniz: "GTAB", dužina = 4
  

2. Definicija stanja DP

Neka dp[i][j] predstavlja dužinu LCS-a prvih i karaktera niza X i prvih j karaktera niza Y.

Prelazi:

• Ako su poslednji karakteri jednaki: dp[i][j] = dp[i-1][j-1] + 1
• Ako nisu jednaki: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Osnovni slučajevi:

• dp[0][j] = 0 za sve j
• dp[i][0] = 0 za sve i

Detaljno objašnjenje problema Najdužeg zajedničkog podniza (LCS)

Problem najdužeg zajedničkog podniza (LCS – Longest Common Subsequence) jedan je od najvažnijih i najčešćih primera korišćenja dinamičkog programiranja. Datа su dva niza (često stringovi), a cilj je pronaći najduži podniz koji se pojavljuje u oba niza zadržavajući isti redosled elemenata, ali bez obaveze da budu uzastopni.

Šta je zapravo LCS?

Ako su zadati nizovi X = „ABCBDAB“ i Y = „BDCABA“, jedan od najdužih zajedničkih podnizova jeste BCBA, dužine 4. Važno je da elementi LCS-a moraju biti u istom redosledu u oba niza, ali između njih mogu da postoje preskočeni karakteri.

Zašto naivno rešenje nije efikasno?

Naivan pristup bi pokušao da generiše sve podnizove niza X (njih ima 2ⁿ), proveri koji se nalaze u Y i pronađe najduži. Međutim, broj podnizova raste eksponencijalno — za string od 30 karaktera postoji milijardu podnizova. U praksi je to neizvodljivo, pa je potrebna efikasnija metoda.

Zašto koristimo dinamičko programiranje?

Ključna ideja je da se problem LCS-a može podeliti na manje podprobleme. Dužina LCS-a za prefikse X[1…i] i Y[1…j] zavisi samo od LCS-a njihovih manjih prefiksa. Upravo zato kreiramo DP matricu gde svaki element predstavlja rezultat jednog podproblema koji se kasnije koristi za gradnju konačnog rešenja.

Definicija DP stanja

Neka dp[i][j] predstavlja dužinu LCS-a prvih i karaktera niza X i prvih j karaktera niza Y. Matrica dp se popunjava od najmanjih ka većim prefiksima.

Osnovni slučajevi

dp[0][j] = 0  (prazan niz nema zajednički podniz)
dp[i][0] = 0
    

Logika popunjavanja DP matrice

1) Ako se poslednji karakteri poklapaju

Ako važi X[i] == Y[j], onda taj karakter mora biti deo LCS-a. Zato je prelaz:

dp[i][j] = dp[i-1][j-1] + 1
    

2) Ako se poslednji karakteri ne poklapaju

Ako se X[i] ≠ Y[j], onda taj karakter ne može biti deo LCS-a. Zbog toga biramo bolji od dva moguća izbora:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

Ovo znači: ili izbacujemo poslednji karakter X-a, ili poslednji karakter Y-a, i uzimamo najbolje rešenje od ta dva podproblema.

Kako izgleda DP matrica u praksi?

Za stringove dužina m i n, kreira se tabela dimenzija (m+1) × (n+1). Prvi red i prva kolona su nule. Svako polje se popunjava koristeći gore navedena pravila. Na kraju je dp[m][n] dužina najdužeg zajedničkog podniza.

Zašto je ovo efikasno?

DP pristup radi u vremenu O(m × n), što je ogromno ubrzanje u poređenju sa eksponencijalnim pristupom. Na primer, za dva stringa od 1000 karaktera DP izvršava oko milion operacija – to je trenutno u računarskom vremenu.

Sažetak DP rešenja

Stanje:        dp[i][j] = LCS(X[1..i], Y[1..j])
Baza:          dp[0][*] = dp[*][0] = 0
Poklapanje:    dp[i][j] = dp[i-1][j-1] + 1
Nepoklapanje:  dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

Ovo je najpoznatiji klasični primer dinamičkog programiranja i priprema učenike za mnoge druge napredne algoritme koji koriste istu logiku podele problema na manje podprobleme sa preklapanjem.

Primer popunjavanja DP matrice za LCS

Uzećemo konkretan primer: X = "ABCBDAB", Y = "BDCABA". Matrica ispod prikazuje kako se korak po korak popunjava DP tabela. Redovi odgovaraju karakterima niza X, a kolone karakterima niza Y.

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

Konačan rezultat se nalazi u donjem desnom uglu matrice: dp[7][6] = 4, što znači da je dužina LCS-a jednaka 4.

Pseudokod za LCS algoritam

function LCS(X, Y):

    # Uzimamo dužine oba stringa
    m = dužina(X)
    n = dužina(Y)

    # Kreiramo DP matricu u kojoj će dp[i][j] da predstavlja
    # dužinu LCS-a za prve i karaktera X i prve j karaktera Y.
    # Matrica ima (m+1) redova i (n+1) kolona zbog slučajeva kada je
    # jedan od stringova "prazan".
    kreiraj matricu dp dimenzija (m+1) × (n+1)

    # Inicijalizacija baze DP-a:
    # Ako je jedan od stringova dužine 0, LCS je uvek 0.
    for i = 0..m:
        dp[i][0] = 0
    for j = 0..n:
        dp[0][j] = 0

    # Popunjavanje DP matrice red po red, kolonu po kolonu
    for i = 1..m:
        for j = 1..n:

            # Ako su trenutno posmatrani karakteri jednaki,
            # oni čine deo LCS-a. Zato dodajemo 1 rešenju
            # prethodnih prefiksa (i-1, j-1).
            if X[i] == Y[j]:
                dp[i][j] = dp[i-1][j-1] + 1

            # Ako se karakteri ne poklapaju, onda se najbolji LCS
            # dobija tako što izbacimo ili:
            #  - poslednji karakter iz X  (dp[i-1][j])
            #  - poslednji karakter iz Y  (dp[i][j-1])
            # Uzimamo maksimum ove dve opcije.
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Krajnji rezultat — dužina LCS-a — nalazi se
    # u donjem desnom ćošku matrice.
    return dp[m][n]

    

Python implementacija

def lcs(X, Y):
    m = len(X)
    n = len(Y)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]
    

C++ implementacija

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lcs(string X, string Y) {
    int m = X.size();
    int n = Y.size();

    vector> dp(m + 1, vector(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {

            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;

            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}
    

3. Tabulacija i analiza rešenja

Popunjavanje DP tabele se vrši redom (bottom-up). Na kraju, dp[n][m] sadrži dužinu najdužeg zajedničkog podniza.

// DP: Najduži zajednički podniz (LCS)
#include 
#include 
#include 
using namespace std;

int main() {
    // Dati stringovi
    string X = "AGGTAB";
    string Y = "GXTXAYB";

    // n i m su njihove dužine
    int n = X.size();
    int m = Y.size();

    // DP tabela dimenzija (n+1) × (m+1)
    // dp[i][j] predstavlja dužinu LCS-a između
    // prvih i karaktera stringa X i prvih j karaktera stringa Y.
    vector> dp(n+1, vector(m+1, 0));

    // Popunjavanje DP matrice — bottom-up pristup.
    // Krećemo od (1,1) jer je prvi red i prva kolona već 0
    // (bazični slučaj: poređenje sa praznim stringom → LCS = 0).
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {

            // Ako su karakteri isti — deo su LCS-a
            // pa dodajemo 1 rezultatu prethodnih prefiksa.
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;

            // Ako nisu isti — uzimamo najbolji rezultat
            // između:
            // 1) izbacivanja poslednjeg karaktera iz X → dp[i-1][j]
            // 2) izbacivanja poslednjeg karaktera iz Y → dp[i][j-1]
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // LCS dužina se nalazi u donjem desnom uglu DP tabele
    cout << "Duzina LCS-a: " << dp[n][m] << endl;

    // ----------------------------------------------
    //  Opcionalno: Rekonstrukcija stvarnog LCS-a.
    //  Krecemo od dp[n][m] i "vracamo se unazad" kroz DP tabelu.
    // ----------------------------------------------

    string lcs = "";
    int i = n, j = m;

    // Dok se nismo vratili do nultog reda ili kolone
    while(i > 0 && j > 0) {

        // Ako su karakteri jednaki -- oni su deo LCS-a.
        // Dodajemo ih na početak rezultata.
        if(X[i-1] == Y[j-1]) {
            lcs = X[i-1] + lcs;
            i--;
            j--;
        }

        // Ako nisu jednaki, pomeramo se u onom smeru
        // gde je LCS duži (ka većoj vrednosti u DP tabeli).
        else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    // Ispis konačnog rekonstruisanog LCS niza
    cout << "LCS: " << lcs << endl;

    return 0;
}
  

Analiza:
– Vreme izvršavanja: O(n*m)
– Memorija: O(n*m) (može da se optimizuje na O(min(n,m)) korišćenjem samo dva reda)
– Primer prikazuje i rekonstrukciju samog podniza.

4. Povezane stranice

• Uvod u DP — osnovna ideja
• DP: Fibonacci sa memoizacijom
• DP: Problem ranca (Knapsack problem)
• DP: Subset Sum (uskoro)

Sledeća lekcija može biti Subset Sum problem ili dodatni primeri LCS-a za vežbu i takmičenja.

Težak zadatak za vežbu — nivo SIO / Državno takmičenje

Sledeći zadatak je namenjen za naprednu praksu i zahteva primenu LCS koncepta na veće ulazne nizove.

Zadatak: Najduži zajednički podniz više nizova

Dat je skup od k stringova: S1, S2, ..., Sk. Cilj je pronaći dužinu najdužeg zajedničkog podniza koji se pojavljuje u svim stringovima.

Primer:

k = 3
S1 = "AGGTAB"
S2 = "GXTXAYB"
S3 = "GTTAB"
Najduži zajednički podniz svih stringova: "GTAB", dužina = 4
  

Uputstvo za rešavanje

• Razmisli kako se standardni LCS između dva stringa može proširiti na više nizova.
• Definiši DP stanje, npr. dp[i1][i2][...][ik] ili alternativno koristi iterativnu redukciju na parove stringova.
• Identifikuj bazne slučajeve: prazan string daje dužinu 0.
• Koristi bottom-up tabulaciju ili memoizaciju (top-down) da popuniš tabelu i izračunaš dužinu LCS.
• Analiziraj memorijske i vremenske složenosti — za veće ulaze može biti potrebna optimizacija ili redukcija dimenzija.

Napomena: Ovaj zadatak je odlična vežba za pripremu za SIO i državna takmičenja. Pokušaj prvo da osmisliš DP pristup i prelaze, a zatim implementiraj kod. Ne gledaj rešenje unapred.

Savet: Ako se želiš dodatno pripremiti, prvo reši standardni LCS za dva stringa sa rekonstrukcijom podniza, pa zatim proširi na više stringova.

Zadatak: Najduži zajednički podniz više nizova

Opis zadatka:

Dat je skup od k stringova: S1, S2, ..., Sk. Cilj je pronaći dužinu najdužeg zajedničkog podniza koji se pojavljuje u svim stringovima.

Primer:

• k = 3
• S1 = "AGGTAB"
• S2 = "GXTXAYB"
• S3 = "GTTAB"

Najduži zajednički podniz svih stringova: "GTAB", dužina = 4.

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje

1. Proširi standardni LCS na više nizova.
2. Za 3 stringa koristi 3D DP: dp[i][j][t].
3. Bazni slučajevi → indeks 0 daje LCS = 0.
4. Prelazi:
   • ako su S1[i] = S2[j] = S3[t] → dp[i][j][t] = dp[i-1][j-1][t-1] + 1
   • inače → maksimum između tri susedne vrednosti
5. Analiziraj kompleksnost: O(n₁ · n₂ · n₃).

Rešenje (C++): LCS za tri stringa — 3D DP

// LCS za tri stringa — C++ implementacija sa komentarima
#include 
#include 
#include 
#include 
using namespace std;

int main() {
    string A = "AGGTAB";
    string B = "GXTXAYB";
    string C = "GTTAB";

    int n = A.size(), m = B.size(), p = C.size();

    // 3D DP tabela dimenzija (n+1) × (m+1) × (p+1)
    vector>> dp(
        n + 1,
        vector>(m + 1, vector(p + 1, 0))
    );

    // Popunjavanje bottom-up
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 1; k <= p; k++) {

                if(A[i-1] == B[j-1] && A[i-1] == C[k-1]) {
                    // Karakter se poklapa u sva tri stringa → deo LCS-a
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                } else {
                    // Uzmi najbolji rezultat iz tri pravca
                    dp[i][j][k] = max({
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    });
                }
            }
        }
    }

    cout << "Duzina LCS-a: " << dp[n][m][p] << endl;

    // --- Rekonstrukcija LCS-a ---
    string lcs = "";
    int i = n, j = m, k = p;

    while(i > 0 && j > 0 && k > 0) {
        if(A[i-1] == B[j-1] && A[i-1] == C[k-1]) {
            lcs.push_back(A[i-1]);
            i--; j--; k--;
        } else {
            int v1 = dp[i-1][j][k];
            int v2 = dp[i][j-1][k];
            int v3 = dp[i][j][k-1];

            if(v1 >= v2 && v1 >= v3) i--;
            else if(v2 >= v1 && v2 >= v3) j--;
            else k--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    cout << "LCS string: " << lcs << endl;
    return 0;
}
    

×

Unos šifre

Ova sekcija je za nastavnike. Unesite šifru za prikaz rešenja:

Pogrešna šifra.

Potvrdi Otkaži

Još jedan napredni zadatak za vežbu — nivo SIO / Državno takmičenje

Ovaj zadatak kombinuje LCS sa dodatnom operacijom — brojanje različitih LCS podnizova.

Zadatak: Brojanje različitih LCS podnizova

Dat su dva stringa X i Y. Tvoj zadatak je da izračunaš koliko različitih podnizova maksimalne dužine LCS postoji.

Primer:

X = "ABCBDAB"
Y = "BDCABA"
Maksimalna dužina LCS = 4
Broj različitih LCS podnizova = 3
  

Uputstvo za rešavanje

• Prvo reši standardni LCS da izračunaš dužinu najdužeg zajedničkog podniza.
• Definiši DP stanje koje čuva ne samo dužinu LCS do indeksa i,j, već i broj različitih podnizova iste dužine.
• Koristi bottom-up ili top-down pristup sa memoizacijom da popuniš tabelu.
• Prati bazne slučajeve: prazan string daje dužinu 0 i broj podnizova 1.
• Pazi na duplikate: ako dva puta dođeš do istog LCS-a, broji ga samo jednom.
• Na kraju, dp[n][m] sadrži broj različitih LCS podnizova maksimalne dužine.

Napomena: Ovaj zadatak je odlična vežba za naprednu primenu DP i zahteva dobru analizu prelaza i optimizaciju memorije.

Savet: Pokušaj prvo da rešiš problem za male stringove i proveri rezultate ručno, pre nego što implementiraš za veće ulaze.

Zadatak (napredni): Brojanje različitih LCS podnizova (SIO / državno)

Opis: Dat su dva stringa X i Y. Potrebno je izračunati:

• maksimalnu dužinu LCS-a (standardni LCS), i
• koliko različitih podnizova te maksimalne dužine postoji.

Primer:

• X = ABCBDAB
• Y = BDCABA

Maksimalna dužina LCS = 4
Broj različitih LCS podnizova = 3

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje

1. Prvo izračunaj dužinu LCS (klasični DP sa tabelom len[i][j]).
2. Zatim definiši DP koji čuva i broj različitih LCS-ova maksimalne dužine: cnt[i][j] = broj različitih LCS podnizova za prefikse X[0..i-1], Y[0..j-1].
3. Bazni slučajevi: za prazne prefikse (i=0 ili j=0) važi len=0 i cnt=1 (postoji tačno jedan „prazan“ podniz).
4. Ključ: kada karakteri nisu isti, može se desiti da se isti LCS dobije kroz dve različite „grane“ (gore/levo). Zbog toga je potrebno uklanjanje duplikata (inclusion–exclusion) pri brojanju.
5. Na kraju, odgovor je cnt[n][m] (broj različitih LCS podnizova) uz proveru da računamo samo one koji imaju dužinu len[n][m].

Savet: testiraj prvo na malim stringovima i ručno ispiši sve LCS podnizove da potvrdiš da brojanje ne duplira iste rezultate.

Rešenje (C++): Brojanje različitih LCS podnizova (sa komentarima)

// Brojanje različitih LCS podnizova za dva stringa (X i Y)
// Ideja: vodimo dve tabele:
//   len[i][j]  - dužina LCS-a za prefikse X[0..i-1], Y[0..j-1]
//   cnt[i][j]  - broj različitih LCS podnizova te maksimalne dužine

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABA";

    int n = (int)X.size();
    int m = (int)Y.size();

    // Tabele dimenzija (n+1) x (m+1)
    vector> len(n + 1, vector(m + 1, 0));
    vector> cnt(n + 1, vector(m + 1, 0));

    // Bazni slučajevi:
    // Kada je i=0 ili j=0, LCS dužina je 0,
    // a postoji tačno jedan "prazan" podniz (brojanje startuje od 1).
    for (int i = 0; i <= n; ++i) {
        cnt[i][0] = 1;
    }
    for (int j = 0; j <= m; ++j) {
        cnt[0][j] = 1;
    }

    // Popunjavanje DP (bottom-up)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {

            if (X[i-1] == Y[j-1]) {
                // Ako se poslednji znakovi poklapaju:
                // dužina LCS se povećava za 1 u odnosu na (i-1, j-1)
                len[i][j] = len[i-1][j-1] + 1;

                // Svi LCS podnizovi na (i-1, j-1) proširuju se istim znakom,
                // pa je broj različitih LCS-ova isti kao cnt[i-1][j-1]
                cnt[i][j] = cnt[i-1][j-1];
            }
            else {
                // Ako se ne poklapaju, dužina je maksimum između dve opcije:
                // (i-1, j) i (i, j-1)
                len[i][j] = max(len[i-1][j], len[i][j-1]);

                long long ways = 0;

                // Dodajemo broj rešenja iz onih susednih stanja koja daju maksimalnu dužinu
                if (len[i-1][j] == len[i][j]) {
                    ways += cnt[i-1][j];
                }
                if (len[i][j-1] == len[i][j]) {
                    ways += cnt[i][j-1];
                }

                // Ako su obe grane (gore i levo) doprinele istim LCS-ovima,
                // postoji preklapanje: isti podnizovi se mogu pojaviti i kroz (i-1, j-1).
                // Zbog toga oduzimamo duplikate (inclusion-exclusion).
                if (len[i-1][j] == len[i][j] &&
                    len[i][j-1] == len[i][j] &&
                    len[i-1][j-1] == len[i][j]) {
                    ways -= cnt[i-1][j-1];
                }

                // Bezbedno: ne želimo negativne vrednosti (u validnim ulazima ne bi trebalo).
                cnt[i][j] = max(0LL, ways);
            }
        }
    }

    cout << "Maksimalna duzina LCS: " << len[n][m] << "\n";
    cout << "Broj razlicitih LCS podnizova: " << cnt[n][m] << "\n";

    return 0;
}
    

Zašto ovaj pristup radi (intuitivno):

• len[i][j] obezbeđuje da brojimo samo podnizove koji su zaista maksimalne dužine.
• cnt[i][j] broji koliko ih postoji, ali se duplikati uklanjaju kada “gore” i “levo” vode do istog skupa LCS-ova.
• Ovo je tipičan obrazac za “brojanje različitih optimalnih rešenja” u DP problemima.

×

Unos šifre

Za prikaz rešenja unesite šifru:

Pogrešna šifra.

Potvrdi Otkaži

Napomena: zaštita je klijentska (JS) — za pravu zaštitu potreban je server-side pristup.

---

Prethodno
​|< DP: Problem ranca (Knapsack problem)

Sledeće
DP: Subset Sum problem >|

---