Najduži zajednički podniz

Problem pronalaska najdužeg zajedničkog podniza ili najduže zajedničke podniske (engl. longest common subsequence problem) predstavlja algoritamski problem u kojem je potrebno odrediti najdužu podnisku koja je zajednička svim niskama u skupu niski (koji čine najčešće dve niske). Podniska neke niske simbola se dobija uklanjanjem nula ili više simbola iz date niske, pri čemu neuklonjeni simboli zadržavaju svoj originalni međusobni redosled. Na primer, za dve niske "btmatmac" i "mtamtab", najduže zajedničke podniske su, između ostalih, "mata" i "mama". Problem pronalaska najduže zajedničke podniske ima primenu u programima koji se bave kompresijom podataka, kao i u bioinformatici.

Uvod

Podniz datog niza je jednostavno dati niz sa nula ili više izostavljenih elemenata. Formalno, ukoliko imamo niz $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ tada je niz $Z=\left\{z_{1},z_{2},\dots ,z_{k}\right\}$ podniz niza $X$ ako postoji strogo rastući niz indeksa $(i_{1},\dots ,i_{k})$ niza $X$ takav da za svako $j=1,\dots ,k$ važi $x_{i_{j}}=z_{j}$. Na primer, niz $Z=\left({\text{B,C,D,B}}\right)$ je podniz niza $X=\left({\text{A,B,C,D,B,A,B}}\right)$ sa odgovarajućim nizom indeksa $(2,3,5,7)$.

Ukoliko imamo dva niza $X$ i $Y$, niz $Z$ nazivamo zajedničkim podnizom nizova $X$ i $Y$ ukoliko je niz $Z$ ujedno podniz niza $X$ i podniz niza $Y$. Na primer, ako je $X=\left({\text{A,B,C,D,B,A,B}}\right)$ i $Y=\left({\text{B,D,C,A,B,A}}\right)$ tada je niz $\left({\text{B,C,A}}\right)$ zajednički podniz nizova $X$ i $Y$. Međutim, niz $\left({\text{B,C,A}}\right)$ nije najduži zajednički podniz nizova $X$ i $Y$. Niz $\left({\text{B,C,B,A}}\right)$ je najduži zajednički podniz nizova $X$ i $Y$, kao što je i niz $\left({\text{B,D,A,B}}\right)$ jer nizovi $X$ i $Y$ nemaju zajeničkih podnizova dužine 5 ili veće.

Problem najduži zajednički podniz (NZP) predstavlja pronalaženje zajedničkog podniza maksimalne dužine unapred zadatih nizova $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ i $Y=\left\{y_{1},y_{2},\dots ,y_{n}\right\}$.

Karakterizacija najdužeg zajedničkog podniza

U pokušaju da rešimo NZP problem grubom silom, prvo bismo numerisali sve podnizove niza $X$ i onda bismo proverili da li je svaki od njih ujedno i podniz niza $Y$, pamteći najduži koji smo do tog trenutka pronašli. Svakom podnizu niza $X$ odgovara podskup indeksa $\left\{1,\dots ,m\right\}$ niza $X$. Obzirom da niz $X$ ima $2^{m}$ podnizova, ovakav pristup zahteva eksponencijalno vreme što ga čini nepraktičnim za dugačke nizove.

NZP problem ima svojstvo optimalnog potproblema, što dokazuje sledeća teorema. Prirodne klase potproblema odgovoraju parovima prefiksa polaznih nizova. Preciznije, ako imamo niz $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ definišimo $i$-ti prefiks od $X$ za svako $i=1,\dots ,m$ kao $X_{i}=\left(x_{1},\dots ,x_{i}\right)$. Na primer, ako je $X=\left({\text{A,B,C,D,B,A,B}}\right)$ tada je $X_{4}=\left({\text{A,B,C,D}}\right)$ i $X_{0}$ je prazan niz.

Teorema

Neka su dati nizovi $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ i $Y=\left\{y_{1},y_{2},\dots ,y_{n}\right\}$, i neka je $Z=\left(z_{1},\dots ,z_{k}\right)$ bilo koji najduži zajednički podniz (NZP) nizova $X$ i $Y$. Tada:

1. Ako $x_{m}=y_{n}$, onda $z_{k}=x_{m}=y_{n}$ i $Z_{k-1}$ je NZP nizova $X_{m-1}$ i $Y_{n-1}$.
2. Ako $x_{m}\neq y_{n}$, onda $z_{k}\neq x_{m}$ i $Z$ je NZP nizova $X_{m-1}$ i $Y$.
3. Ako $x_{m}\neq y_{n}$, onda $z_{k}\neq y_{n}$ i $Z$ je NZP nizova $X$ i $Y_{n-1}$.

Dokaz

(1) Ako je $z_{k}\neq x_{m}$ onda možemo da nadovežemo $x_{m}=y_{n}$ na $Z$ čime bismo dobili zajednički podniz nizova $X$ i $Y$ dužine $k+1$, što je u kontradikciji sa pretpostavkom da je $Z$ najduži zajednički podniz. Stoga, mora da važi $z_{k}=x_{m}=y_{n}$. Prefiks $Z_{k-1}$ je zajednički podniz nizova $X_{m-1}$ i $Y_{n-1}$ dužine $k-1$, i još ostaje da se pokaže da je NZP. Pretpostavimo da postoji zajednički podniz $W$ nizova $X_{m-1}$ i $Y_{n-1}$ sa dužinom većom od $k-1$. Tada, nadovezujući $x_{m}=y_{n}$ na $W$ dobijamo zajednički podniz dužine veće od $k$, što je u kontradikciji sa pretpostavkom da je $Z$ NZP.

(2) Ako $z_{k}\neq x_{m}$, onda je $Z$ je zajednički podniz nizova $X_{m-1}$ i $Y$. Ako bi postojao zajednički podniz $W$ nizova $X_{m-1}$ i $Y$ dužine veće od $k$, onda bi $W$ bio zajednički podniz nizova $X_{m}$ i $Y$, što je u kontradikciji sa pretpostavkom da je $Z$ NZP nizova $X$ i $Y$.

(3) Simetrično drugom slučaju.

Način na koji teorema karakteriše najduži zajednički podniz govori nam da NZP dva niza u sebi sadrži i NZP prefiksa ta dva niza. Stoga, prblem NZP ima svojstvo optimalnog potproblema.

Rekurzivno rešenje

Teorema nam govori da treba da ispitamo ili jedno ili dva potproblema kada pronalazimo najduži zajednički podniz nizova $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ i $Y=\left\{y_{1},y_{2},\dots ,y_{n}\right\}$. Ako je $x_{m}=y_{n}$ onda moramo da pronađemo NZP nizova $X_{m-1}$ i $Y_{n-1}$. Nadovezujući $x_{m}=y_{n}$ na pronađeni NZP dobićemo najduži zajednički podniz nizova $X$ i $Y$. Ako $x_{m}\neq y_{n}$, onda moramo da rešimo dva potproblema: moramo da pronađemo NZP nizova $X_{m-1}$ i $Y$ i NZP nizova $X$ i $Y_{n-1}$. Duži od dva pronađena najmanja zajednička podniza je NZP polaznih nizova $X$ i $Y$.

Lako se uočava da se potproblemi problema NZP međusobno prepliću. Kako bismo pronašli NZP nizova $X$ i $Y$, možda treba da pronađemo i najduže zajedničke podnizove nizova $X_{m-1}$ i $Y$ i nizova $X$ i $Y_{n-1}$. Ali, svaki od ova dva potproblema za potproblem ima pronalazak najmanjeg zajedničkog podniza nizova $X_{m-1}$ i $Y_{n-1}$. Mnogi drugi potproblemi dele svoje potprobleme.

Rekurzivno rešenje NZP problema obuhvata i kreiranje rekurentne relacije za pronalaženje optimalnog rešenja. Definišimo $c\left[i,j\right]$ kao dužinu NZP nizova $X_{i}$ i $Y_{j}$. Ako je $i=0$ ili $j=0$, onda jedan od nizova ima dužinu $0$, čime je i NZP dužine $0$. Opitimalni potproblem NZP problema daje sledeću rekurentnu relaciju:

$c\left[i,j\right]={\begin{cases}0,&{\text{ako }}i=0{\text{ ili }}j=0\\c\left[i-1,j-1\right]+1&{\text{ako }}i,j>0{\text{ i }}x_{i}=y_{j}\\\max \left(c\left[i,j-1\right],c\left[i-1,j\right]\right)&{\text{ako }}i,j>0{\text{ i }}x_{i}\neq y_{j}\end{cases}}$

Primetimo da u rekurentnoj relaciji uslov u problemu određuje koji potproblem ćemo da razmatramo. Kada je $x_{i}=y_{j}$, tada treba da razmatramo potproblem koji predstavnja traženje najdužeg zajedničkog podniza nizova $X_{i-1}$ i $Y_{j-1}$. U suprotnom, razmatraćemo dva potproblema, jedan je pronalaženje NZP nizova $X_{i}$ i $Y_{j-1}$ i NZP nizova $X_{i-1}$ i $Y_{j}$.

Izračunavanje dužine najdužeg zajedničkog podniza

Uz pomoć gore navedene rekurentne relacije lako možemo da napišemo rekurzivni algoritam koji će izračunavati dužinu najdužeg zajedničkog podniza dva niza u eksponencijalnom vremenu. Obzirom da NZP problem ima samo $\Theta \left(mn\right)$ različitih potproblema možemo da iskoristimo dinamičko programiranje za izračunavanje rešenja odozdo nagore.

Procedura LCS_length kao ulazne argumente ima dva niza $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ i $Y=\left\{y_{1},y_{2},\dots ,y_{n}\right\}$. Procedura čuva vrednosti $c\left[i,j\right]$ u matrici $c\left[0\dots m,0\dots n\right]$, tako što redom po vrstama sleva nadesno izračunava dužine najdužih zajedničkih podnizova nizova $X_{i}$ i $Y_{j}$. Procedura takođe održava i pomoćnu matricu $b\left[1\dots m,1\dots n\right]$ koju koristimo pri konstrukciji najdužeg zajedničkog podniza. Intuitivno, $b\left[i,j\right]$ pokazuje na zapis u matrici koji odgovara optimalnom rešenju izabranog potproblema prilikom izračunavanja $c\left[i,j\right]$. Procedura vraća matrice $b$ i $c$, pri čemu $c\left[m,n\right]$ sadrži dužinu najdužeg zajedničkog podniza nizova $X$ i $Y$.

Definišimo sledeće simbole:

${\text{GORELEVO }}\nwarrow$

${\text{GORE }}\uparrow$

${\text{LEVO }}\leftarrow$

LCS_length(X, Y)

m = X.dužina
n = Y.dužina
neka su b[1 .. m, 1 .. n] i c[0 .. m, 1 .. n] prazne matrice

for i = 1 do m
   c[i,0] = 0
for j = 0 do n
   c[0,j] = 0

for i = 1 do m
   for j = 1 do n
      if x[i] == y[j]
         c[i,j] = c[i-1,j-1] + 1
         b[i,j] = GORELEVO
      else if c[i-1,j] >= c[i, j-1]
         c[i,j] = c[i-1, j]
         b[i,j] = GORE
      else
         c[i,j] = c[i, j-1]
         b[i,j] = LEVO

return b i c

Vreme izvršavanja prikazane procedure je $\Theta \left(mn\right)$, jer svaki unos u matricu zahteva $\Theta \left(1\right)$ koraka prilikom izvršavanja.

Konstruisanje najdužeg zajedničkog podniza

Matrica $b$ koju vraća procedura LCS_length omogućava nam da brzo konstruišemo NZP nizova $X=\left\{x_{1},x_{2},\dots ,x_{m}\right\}$ i $Y=\left\{y_{1},y_{2},\dots ,y_{n}\right\}$. Jednostavno krenemo od $b\left[m,n\right]$ i samo se krećemo kroz matricu prateći strelice. Kada god naiđemo na strelicu $\nwarrow$ na polju $b\left[i,j\right]$ to znači da je $x_{i}=y_{j}$ element najdužeg zajedničkog podniza nizova $X$ i $Y$ koji je procedura LCS_length pronašla. Ovim pristupom otkrivamo elemente NZP nizova $X$ i $Y$ u obrnutom poretku. Sledeća rekurzivna procedura štampa elemente NZP nizova $X$ i $Y$ u originalnom poretku. Poziv procedure je sledeći LCS_print(b, X, X.dužina, Y.dužina).

LCS_print(b,X,i,j)

if i == 0 ili j == 0
   return
if b[i,j] == GORELEVO
   LCS_print(b, X, i-1, j-1)
   print X[i]
else if b[i,j] == GORE
   LCS_print(b, X, i-1, j)
else
   LCS_print(b, X, i, j-1)

Proceduri LCS_print je potrebno $\mathrm {O} \left(m+n\right)$ koraka za izvršavanje, jer se u svakom rekurzivnom pozivu smanjuje barem jedan od indeksa $i$ i $j$.

Unapređenja

U NZP algoritmu moguće je potpuno eliminisati matricu $b$. Svaki $c\left[i,j\right]$ zavisi samo od još tri zapisa u matrici $c$: $c\left[i-1,j-1\right]$,$c\left[i-1,j\right]$ i $c\left[i,j-1\right]$. Ukoliko imamo vrednost $c\left[i,j\right]$, onda možemo u konstantnom vremenu da utvrdimo koja od ove tri vrednosti je bila iskorišćena prilikom izračunavanja $c\left[i,j\right]$ bez potrebe da pristupamo elementima matrice $b$. Stoga možemo da rekonstruišemo NZP u vremenu $\mathrm {O} \left(m+n\right)$. Iako ćemo na ovaj način uštedeti $\Theta \left(mn\right)$ prostora, dodatni prostor za izračunavanje najdužeg zajedničkog podniza ne opada asimptotski, jer nam i dalje treba $\Theta \left(mn\right)$ prostora za skladištenje matrice $c$.

Ipak, možemo asimptotski da smanjimo potreban prostor za izračunavanje dužine najdužeg zajedničkog podniza, jer su nam u svakom trenutku potrebne samo dve vrste matrice $c$: vrsta koja se izračunava i prethodno izračunata vrsta. Ovo unapređenje je korisno samo ako nam treba dužina najdužeg zajedničkog podniza, jer smanjena matrica ne sadrži dovoljno informacija za rekonstrukciju samog NZP-a u vremenu $\mathrm {O} \left(m+n\right)$.

Primene

Aplikacije u biologiji često treba da porede DNK lance dva ili više različitih organizama. DNK lanci mogu da se predstave kao konačne reči nad jezikom $\mathrm {L} =\left\{A,C,G,T\right\}$. Jedan od razloga za poređenje DNK lanaca različitih organizama je utvrđivanje njihove međusobne sličnosti, što može da bude mera srodnosti različitih organizama. Sličnost dva lanca može da se meri na različite načine. Jedan od načina kako možemo da izmerimo sličnost dva DNK lanca $S_{1}$ i $S_{2}$ je da pronađemo treći lanac $S_{3}$ u kome se simboli iz jezika $\mathrm {L}$ pojavljuju i u lancima $S_{1}$ i $S_{2}$; simboli moraju da se pojavljuju u istom redosledu ali ne i uzastopno. Što je duži pronađeni lanac $S_{3}$, to su lanci $S_{1}$ i $S_{2}$ sličniji.

Opis rešenja za dve niske

Za pronalazak najduže zajedničke podniske dve niske x i y, izračunavaju se dužine najdužih zajedničkih podniski svih mogućih parova prefiksa, jednog iz niske x i drugog iz niske y. Neka je x = x₁...x_m i y = y₁...y_n. Za svako i = 0,1,...,m i j = 0,1,...,n, najduža zajednička podniska prefiksa x₁...x_i niske x i prefiksa y₁...y_j niske y se može odrediti na sledeći način. Pre svega, ukoliko je i ili j jednako 0, tada jedan od ovih prefiksa mora biti prazna reč, pa je jedina moguća zajednička podniska takva dva prefiksa prazna reč.

Ukoliko su i i j oba veći od 0, posmatraju se dva slučaja u zavisnosti od toga da li su poslednji znakovi dve niske jednaki:

1. Ako je x_i ≠ y_j, tada najduža zajednička podniska dva prefiksa ne može uključiti x_i i y_j, već je ona jednaka dužoj od dve najduže zajedničke podniske - za prefikse x₁...x_i-1 i y₁...y_j, odnosno x₁...x_i i y₁...y_j-1.
2. Ako je x_i = y_j, tada najduža zajednička podniska može uključiti x_i i y_j, koji neće remetiti druga potencijalna vezivanja simbola u dva prefiksa. To znači da je najduža zajednička podniska za prefikse x₁...x_i i y₁...y_j zapravo najduža zajednička podniska za prefikse x₁...x_i-1 i y₁...y_j-1 na koje je nadovezan poslednji simbol koji je isti u dva prefiksa - x_i, odnosno y_j.

Na osnovu ovih zapažanja može se izvesti rekurzivna definicija za dužinu najduže zajedničke podniske prefiksa x₁...x_i i y₁...y_j. Ako tu dužinu označimo sa L(i,j), tada je:

$L(i,j)=\left\{{\begin{matrix}0&i=0\lor j=0\\\max\{L(i,j-1),L(i-1,j)\}&i>0\land j>0\land x_{i}\neq y_{j}\\1+L(i-1,j-1)&i>0\land j>0\land x_{i}=y_{j}\end{matrix}}\right.$

Dužina najduže zajedničke podniske za dve cele niske x i y je L(m,n), što se može izračunati jednostavnim rekurzivnim algoritmom na osnovu prethodne formule. Međutim, vreme izvršavanja takvog algoritma bi bilo eksponencijalno, a razlog za to je činjenica da algoritam više puta računa dužinu najduže zajedničke podniske za iste parove prefiksa.

Rekurzivni algoritam se može znatno ubrzati ako se primeni pristup dinamičkog programiranja i konstruiše tabela L vrednosti dužina L(i,j) za i=0,1,...,m i j=0,1,...,n. Pošto u izračunavanju dužine L(i,j) učestvuju vrednosti L(i,j-1), L(i-1,j) i L(i-1,j-1), tabela se može popunjavati red po red i tako obezbediti da se potrebne vrednosti za L(i,j) nalaze u tabeli. Ovo je ilustrovano na sledećoj slici:

L(i-1,j-1)	L(i-1,j)
L(i,j-1)	L(i,j)

Tabela L se može iskoristiti za određivanje simbola koji čine najdužu zajedničku podnisku. Pošto tabela L sadrži dužine najdužih zajedničkih podniski svih parova prefiksa dve date niske, od donjeg desnog ugla tabele se može formirati put kroz ovu tabelu i na tom putu uzimati određeni simboli. Tako odabrani simboli u obrnutom redosledu predstavljaju najdužu zajedničku podnisku za dve date niske. Ako pretpostavimo da na putu od donjeg desnog ugla tabele L dolazimo do tačke preseka i-te vrste i j-te kolone koja odgovara paru znakova x_i i y_j. Ako je x_i=y_j, onda znakove x_i i y_j smatramo uparenim i znak x_i=y_j dodajemo ispred svih znakova najduže zajedničke podniske koji su do tada nađeni. Na putu u narednom koraku se prelazi dijagonalno levo na gornji red, tj. u red i-1 i kolonu j-1. Ako je x_i≠y_j, vrednost L(i,j) mora biti jednaka jednoj od dužina L(i-1,j) ili L(i,j-1) (ili obema). U prvom slučaju, potrebno je preći na poziciju (i-1,j), a u drugom slučaju na poziciju (i,j-1). U slučaju jednakih vrednosti, na proizvoljan način se bira jedna od dve pozicije.

Primer

Na slici je prikazan rezultat verzije algoritma koja koristi dinamičko programiranje za niske "btmatmac" i "mtamtab". Vrednosti u matrici koje su označene žutom bojom predstavljaju put kojim se određuje najduža zajednička podniska, pa je jedno od mogućih rešenja za ovaj primer podniska "mata".

			b	t	m	a	t	m	a	c
	j\i	0	1	2	3	4	5	6	7	8
	0	0	0	0	0	0	0	0	0	0
m	1	0	0	0	1	1	1	1	1	1
t	2	0	0	1	1	1	2	2	2	2
a	3	0	0	1	1	2	2	3	3	3
m	4	0	0	1	2	2	2	3	3	3
t	5	0	0	1	2	2	3	3	3	3
a	6	0	0	1	2	3	3	3	4	4
b	7	0	1	1	2	3	3	3	4	4

Implementacija algoritma u programskom jeziku Java

Rekurzivni algoritam

public static String najduzaZajednickaPodniska(String a, String b){
	 int duzinaA = a.length();
	 int duzinaB = b.length();
	 if(duzinaA == 0 || duzinaB == 0){
	 return "";
	 }else if(a.charAt(duzinaA-1) == b.charAt(duzinaB-1)){
	 return najduzaZajednickaPodniska(a.substring(0,duzinaA-1),b.substring(0,duzinaB-1))
	 + a.charAt(duzinaA-1);
	 }else{
	 String x = najduzaZajednickaPodniska(a, b.substring(0,duzinaB-1));
	 String y = najduzaZajednickaPodniska(a.substring(0,duzinaA-1), b);
	 return (x.length() > y.length()) ? x : y;
	 }
}

Algoritam zasnovan na dinamičkom programiranju

public static String najduzaZajednickaPodniska(String a, String b) {
	 int[][] duzine = new int[a.length()+1][b.length()+1];
	 
	 // red 0 and kolona 0 su vec inicijalizovane na 0
	 
	 for (int i = 0; i < a.length(); i++)
	 for (int j = 0; j < b.length(); j++)
	 if (a.charAt(i) == b.charAt(j))
	 	duzine[i+1][j+1] = duzine[i][j] + 1;
	 else
	 	duzine[i+1][j+1] =
	 Math.max(duzine[i+1][j], duzine[i][j+1]);
	 
	 // citamo simbole koji cine najduzu zajednicku podnisku
	 StringBuffer sb = new StringBuffer();
	 for (int x = a.length(), y = b.length();
	 x != 0 && y != 0; ) {
	 if (duzine[x][y] == duzine[x-1][y])
	 x--;
	 else if (duzine[x][y] == duzine[x][y-1])
	 y--;
	 else {
	 assert a.charAt(x-1) == b.charAt(y-1);
	 sb.append(a.charAt(x-1));
	 x--;
	 y--;
	 }
	 }
	 
	 return sb.reverse().toString();
}

Implementacija algoritma u programskom jeziku C

Implementacija je u programskom jeziku C uz pretpostavku o maksimalnoj dužini nizova i uz pretpostavku da se radi o nizovima koji sadrže celobrojne vrednosti.

#include <stdio.h>
#include <stdlib.h>
#define UP 1
#define LEFT 2
#define UPLEFT 3
#define MAX_LENGTH 10000

int c[MAX_LENGTH][MAX_LENGTH];
int b[MAX_LENGTH][MAX_LENGTH];
int n;
int m;

void LCS_length(int* x, int *y, int m, int n){
     int i,j;
     
     for (i=0; i<=m; i++){
         for (j=0; j<=n; j++){
             c[i][j] = b[i][j] = 0;    
         }
     }     
     
     for (i=1; i<=m; i++){
         c[i][0] = 0;
         b[i][0] = UP;
     }
         
     for (j=0; j<=n; j++){
         c[0][j] = 0;
         b[0][j] = LEFT;    
     }
         
     for (i=1; i<=m; i++){
         for (j=1; j<=n; j++){
         
             if (x[i-1] == y[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = UPLEFT;         
             }
             else if (c[i-1][j] >= c[i][j-1]){
                  c[i][j] = c[i-1][j];
                  b[i][j] = UP;     
             }
             else {
                  c[i][j] = c[i][j-1];
                  b[i][j] = LEFT;     
             }
         }
     }
}

void LCS_print(int b[][MAX_LENGTH], int* x, int i, int j){
     
     if (i==0 || j == 0)
        return;
     
     if (b[i][j] == UPLEFT){
        LCS_print(b, x, i-1, j-1);
        printf("%d ", x[i]);            
     }
     else if (b[i][j] == UP)
          LCS_print(b, x, i-1, j);
     else
         LCS_print(b, x, i, j-1);
}

int main(int argc, char** argv){
    
    int *x;
    int *y;
    int i;
    
    scanf("%d", &m);
    
    if (m > MAX_LENGTH - 1)
    	m = MAX_LENGTH-1;
    
    if ((x = (int*)malloc(m*sizeof(int))) == NULL)
       exit(EXIT_FAILURE);
       
    for (i=0; i<m; i++)
        scanf("%d", &x[i]);
    
    scanf("%d", &n);
    
    if (n > MAX_LENGTH - 1)
    	n = MAX_LENGTH-1;
    
    if ((y = (int*)malloc(n*sizeof(int))) == NULL)
       exit(EXIT_FAILURE);
       
    for (i=0; i<n; i++)
        scanf("%d", &y[i]);
        
    LCS_length(x,y,m,n);
    LCS_print(b, x, m, n);
    
    free(x);
    free(y);
    
    exit(EXIT_SUCCESS);    
}

Složenost algoritama

Rekurzivni algoritam kojim se određuje najduža zajednička podniska dve niske ima eksponencijalnu složenost. Ako dve niske, za koje je potrebno odrediti najdužu zajedničku podnisku, imaju dužine m, odnosno n i neka je k = m + n, vreme izvršavanja takvog algoritma je θ(2^k).

Složenost algoritma zasnovanom na dinamičkom programiranju za određivanje najduže zajedničke podniske dve niske iznosi Ο(mn).

Literatura

• Dejan Živković, (2007). Osnove dizajna i analize algoritama. CET. ISBN 978-86-7991-327-2.  Poglavlje 7.

Spoljašnje veze

• Implementacija algoritma za određivanje najduže zajedničke podniske u mnogim programskim jezicima
• Dictionary of Algorithms and Data Structures: longest common subsequence
• Implementation of Longest Common Subsequence Algorithm in C Programming Language