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.

Tekst zadatka — Najduži zajednički podniz (LCS)

Datа su dva stringa X i Y. Potrebno je odrediti dužinu najdužeg zajedničkog podniza (Longest Common Subsequence — LCS) između ova dva stringa.

Podniz ne mora biti kontinualan — karakteri se mogu birati sa proizvoljnih pozicija, ali se njihov relativni redosled mora sačuvati.

Ulaz

Prvi red sadrži string X
Drugi red sadrži string Y

Izlaz

Ispisati jedan ceo broj — dužinu najdužeg zajedničkog podniza

Primer

Ulaz:
AGGTAB
GXTXAYB

Izlaz:
4

Objašnjenje:
Jedan od najdužih zajedničkih podnizova je "GTAB".

Napomena

Ako ne postoji nijedan zajednički karakter, rezultat je 0.
Zadatak zahteva samo dužinu LCS-a, ne i sam podniz.

Vizualna interpretacija DP tabele (LCS)

Jedan od najčešćih problema kod razumevanja LCS algoritma jeste kako se popunjava DP tabela i zašto se u nekim slučajevima uzima maksimum iz susednih polja.

Posmatrajmo primer:

X = "AGGTAB"
Y = "GXTXAYB"

Kreiramo DP tabelu dimenzija (|X|+1) × (|Y|+1), gde dp[i][j] predstavlja dužinu LCS-a prefiksa X[0..i-1] i Y[0..j-1].

Početna DP tabela


      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0
   G  0
   G  0
   T  0
   A  0
   B  0

Prvi red i prva kolona su nule, jer LCS sa praznim stringom uvek ima dužinu 0.

Kako se popunjava jedno polje?

Posmatrajmo polje dp[i][j]:

Ako su karakteri jednaki:
X[i-1] == Y[j-1]
tada:
```
dp[i][j] = dp[i-1][j-1] + 1
```
➜ Krećemo se dijagonalno, jer smo produžili zajednički podniz.
Ako karakteri nisu jednaki:
```
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
➜ Biramo bolju od dve opcije:
- preskočiti karakter iz stringa X (gore)
- preskočiti karakter iz stringa Y (levo)

Primer popunjene DP tabele


      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0  0  0  0  0  1  1  1
   G  0  1  1  1  1  1  1  1
   G  0  1  1  1  1  1  1  1
   T  0  1  1  2  2  2  2  2
   A  0  1  1  2  2  3  3  3
   B  0  1  1  2  2  3  3  4

Vrednost u donjem desnom uglu dp[|X|][|Y|] predstavlja dužinu najdužeg zajedničkog podniza. U ovom primeru to je 4.

Zašto gledamo maksimum iz levo i gore?

Kada se karakteri ne poklapaju, trenutni karakter ne može biti deo zajedničkog podniza. Zato ispitujemo dve mogućnosti:

ignorisati karakter iz prvog stringa (gore)
ignorisati karakter iz drugog stringa (levo)

Biramo onu opciju koja daje duži zajednički podniz, jer je cilj maksimizacija dužine LCS-a.

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

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
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	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];
}

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 <iostream>
#include <vector>
#include <string>
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<vector<int>> dp(n+1, vector<int>(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.

Skriveni mini kviz — Najduži zajednički podniz- LCS (Longest Common Subsequence)

Proveri da li razumeš osnovne ideje i DP rešenje za LCS problem.

Otvori kviz

Zadatak — Rekonstrukcija najdužeg zajedničkog podniza (LCS)

Data su dva stringa X i Y. Nakon popunjavanja DP tabele za Longest Common Subsequence (LCS), potrebno je rekonstruisati sam najduži zajednički podniz, a ne samo njegovu dužinu.

Ako postoji više rešenja, dozvoljeno je ispisati bilo koje.

Ulaz

Prvi red: string X
Drugi red: string Y

Izlaz

Jedan string — najduži zajednički podniz

Primer

Ulaz:
AGGTAB
GXTXAYB

Izlaz:
GTAB

Uputstvo — rekonstrukcija LCS-a

Rekonstrukcija LCS-a se vrši kretanjem unazad kroz DP tabelu, počevši od polja dp[n][m].

Ako je X[i-1] == Y[j-1]:
- karakter pripada LCS-u
- dodaje se u rezultat
- pomeramo se dijagonalno: i--, j--
Ako karakteri nisu jednaki:
- ako je dp[i-1][j] > dp[i][j-1] → idemo gore
- inače → idemo levo
Pošto se ide unazad, dobijeni string je obrnut i na kraju se mora okrenuti.


// Pseudokod
while (i > 0 && j > 0):
  if X[i-1] == Y[j-1]:
    dodaj X[i-1] u LCS
    i--, j--
  else if dp[i-1][j] > dp[i][j-1]:
    i--
  else:
    j--

Rešenje — Rekonstrukcija LCS-a (C++)


// Rekonstrukcija Longest Common Subsequence (LCS)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string X, Y;
    cin >> X >> Y;

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

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

    // Popunjavanje DP tabele
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; 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]);
        }
    }

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

    while(i > 0 && j > 0) {
        if(X[i-1] == Y[j-1]) {
            lcs.push_back(X[i-1]);
            i--; j--;
        } else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    cout << lcs << endl;
    return 0;
}

Složenost

Vreme: O(n · m)
Memorija: O(n · m)

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 (3 stringa)

Data su tri stringa A, B i C. Potrebno je pronaći najduži zajednički podniz koji se pojavljuje u sva tri stringa.

Primer

Ulaz:
AGGTAB
GXTXAYB
GTTAB

Izlaz:
GTAB

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


// LCS za tri stringa
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string A, B, C;
    cin >> A >> B >> C;

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

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

    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])
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else
                    dp[i][j][k] = max({
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    });

    cout << dp[n][m][p] << endl;
    return 0;
}

Složenost

Vreme: O(n · m · p)
Memorija: O(n · m · p)

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

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

maksimalnu dužinu najdužeg zajedničkog podniza (LCS)
koliko različitih LCS podnizova te maksimalne dužine postoji

Primer

X = ABCBDAB
Y = BDCABA

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

Rešenje — Brojanje različitih LCS podnizova (C++)


// Brojanje različitih LCS podnizova
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

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

    vector<vector<int>> len(n + 1, vector<int>(m + 1, 0));
    vector<vector<long long>> cnt(n + 1, vector<long long>(m + 1, 0));

    // Bazni slučajevi
    for(int i = 0; i <= n; i++) cnt[i][0] = 1;
    for(int j = 0; j <= m; j++) cnt[0][j] = 1;

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

            if(X[i-1] == Y[j-1]) {
                len[i][j] = len[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
            } else {
                len[i][j] = max(len[i-1][j], len[i][j-1]);

                long long ways = 0;
                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];

                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];
                }

                cnt[i][j] = max(0LL, ways);
            }
        }
    }

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

    return 0;
}

Zašto ovaj pristup radi?

len[i][j] osigurava da brojimo samo optimalne podnizove
cnt[i][j] broji različite LCS-ove bez duplikata
inclusion–exclusion uklanja ponovljene puteve u DP tabeli
obrazac važi za mnoge probleme „brojanja optimalnih rešenja“

Detaljno objašnjenje logike rešenja

Dinamička tabela len određuje koliko je dugačak optimalni LCS, dok tabela cnt računa koliko različitih LCS-ova te dužine postoji.

Svaka ćelija (i, j) predstavlja problem za prefikse X[0..i-1] i Y[0..j-1]. LCS se može formirati:

dijagonalno (↖) – ako se karakteri poklapaju
odozgo (↑) – ako zanemarimo karakter iz X
sleva (←) – ako zanemarimo karakter iz Y

Kada se optimalna dužina može dobiti i odozgo i sleva, iste LCS sekvence se pojavljuju u oba pravca. Zato se primenjuje princip uključenja–isključenja i oduzima se cnt[i-1][j-1].

Na taj način se osigurava da se svaki različit LCS string broji tačno jednom, bez obzira na broj putanja kroz DP tabelu.

Za dati primer postoje tačno tri različita LCS-a dužine 4:


BCBA
BDAB
BCAB

Konkretno grananje u ovom primeru

U ovom zadatku ne postoji samo jedan LCS, već više različitih podnizova iste maksimalne dužine. Na osnovu DP tabele vidi se da postoje tri različite putanje koje daju LCS dužine 4.

Vizuelno (po slovima):

LCS #1
B C B A
LCS #2
B D A B
LCS #3
B C A B

□ Sva tri podniza:

imaju maksimalnu dužinu 4
pojavljuju se kao podnizovi u X i u Y
različiti su kao stringovi

Zašto ih nema više?

Iako u DP tabeli postoji veliki broj različitih putanja od ćelije (n, m) do (0, 0), različite putanje mogu proizvesti isti LCS string.

Na primer, sledeće dve putanje:

↖ ↑ ← ↖     i     ↖ ← ↑ ↖

mogu voditi do istog niza karaktera. Iako su putanje različite, rezultat (LCS string) je isti, pa se mora brojati samo jednom.

Kako se to rešava algoritamski (intuicija)

Pored standardne DP tabele za dužinu:


dpLen[i][j] = dužina LCS-a za X[0..i-1] i Y[0..j-1]

uvodi se i druga tabela:


dpCount[i][j] = broj različitih LCS podnizova
               maksimalne dužine

Osnovna pravila:

Ako su karakteri jednaki:
```
count[i][j] = count[i-1][j-1]
      
```
Svaki optimalni LCS se produžava za taj zajednički karakter.
Ako karakteri nisu jednaki:
- Ako je dpLen[i-1][j] > dpLen[i][j-1]:
```
count[i][j] = count[i-1][j]
          
```
- Ako je dpLen[i][j-1] > dpLen[i-1][j]:
```
count[i][j] = count[i][j-1]
          
```
- Ako su dužine jednake:
```
count[i][j] = count[i-1][j] + count[i][j-1]
              - count[i-1][j-1]
          
```
  Oduzimanjem count[i-1][j-1] uklanjaju se duplikati koji dolaze iz oba pravca.

□ Oduzimanje je ključno – bez njega bi se isti LCS podniz prebrojavao više puta.

Konačan rezultat za dati primer


X = ABCBDAB
Y = BDCABA

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

4. Povezane stranice

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

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

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

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

Tekst zadatka — Najduži zajednički podniz (LCS)

Ulaz

Izlaz

Primer

Napomena

Vizualna interpretacija DP tabele (LCS)

Početna DP tabela

Kako se popunjava jedno polje?

Primer popunjene DP tabele

Zašto gledamo maksimum iz levo i gore?

Opis problema

Definicija stanja DP

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

Šta je zapravo LCS?

Zašto naivno rešenje nije efikasno?

Zašto koristimo dinamičko programiranje?

Definicija DP stanja

Osnovni slučajevi

Logika popunjavanja DP matrice

1) Ako se poslednji karakteri poklapaju

2) Ako se poslednji karakteri ne poklapaju

Kako izgleda DP matrica u praksi?

Zašto je ovo efikasno?

Sažetak DP rešenja

Primer popunjavanja DP matrice za LCS

Pseudokod za LCS algoritam

Python implementacija

C++ implementacija

Tabulacija i analiza rešenja

Skriveni mini kviz — Najduži zajednički podniz- LCS (Longest Common Subsequence)

Mini kviz: Najduži zajednički podniz (LCS)

Zadatak — Rekonstrukcija najdužeg zajedničkog podniza (LCS)

Ulaz

Izlaz

Primer

Uputstvo — rekonstrukcija LCS-a

Rešenje — Rekonstrukcija LCS-a (C++)

Složenost

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

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

Uputstvo za rešavanje

Zadatak — Najduži zajednički podniz (3 stringa)

Primer

Uputstvo

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

Složenost

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

Zadatak: Brojanje različitih LCS podnizova

Uputstvo za rešavanje

Zadatak (napredni): Brojanje različitih LCS podnizova

Primer

Uputstvo za rešavanje

Rešenje — Brojanje različitih LCS podnizova (C++)

Zašto ovaj pristup radi?

Detaljno objašnjenje logike rešenja

Konkretno grananje u ovom primeru

Zašto ih nema više?

Kako se to rešava algoritamski (intuicija)

Konačan rezultat za dati primer

4. Povezane stranice

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