Изворни код странице Најдужи заједнички подниз

Проблем проналаска '''најдужег заједничког подниза''' или '''најдуже заједничке подниске''' ({{јез-енгл|longest common subsequence problem}}) представља [[алгоритам]]ски проблем у којем је потребно одредити најдужу подниску која је заједничка свим нискама у скупу ниски (који чине најчешће две ниске). Подниска неке ниске симбола се добија уклањањем нула или више симбола из дате ниске, при чему неуклоњени симболи задржавају свој оригинални међусобни редослед. На пример, за две ниске ''"бтматмац"'' и ''"мтамтаб"'', најдуже заједничке подниске су, између осталих, ''"мата"'' и ''"мама"''. Проблем проналаска најдуже заједничке подниске има примену у програмима који се баве компресијом података, као и у [[Биоинформатика|биоинформатици]].

== Увод ==
Подниз датог низа је једноставно дати низ са нула или више изостављених елемената. Формално, уколико имамо низ <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> тада је низ <math>Z = \left \{ z_1, z_2, \dots , z_k \right \}</math> '''подниз''' низа <math>X</math> ако постоји строго растући низ индекса <math>(i_1, \dots, i_k)</math> низа <math>X</math> такав да за свако <math>j = 1, \dots, k</math> важи <math>x_{i_j} = z_j</math>. На пример, низ <math>Z = \left ( \text {B,C,D,B} \right )</math> је подниз низа <math>X = \left ( \text {A,B,C,D,B,A,B} \right )</math> са одговарајућим низом индекса <math>(2,3,5,7)</math>.

Уколико имамо два низа <math>X</math> и <math>Y</math>, низ <math>Z</math> називамо '''заједничким поднизом''' низова <math>X</math> и <math>Y</math> уколико је низ <math>Z</math> уједно подниз низа <math>X</math> и подниз низа <math>Y</math>. На пример, ако је <math>X = \left ( \text {A,B,C,D,B,A,B} \right )</math> и <math>Y = \left ( \text{B,D,C,A,B,A} \right )</math> тада је низ <math>\left ( \text {B,C,A} \right )</math> заједнички подниз низова <math>X</math> и <math>Y</math>. Међутим, низ <math>\left ( \text{B,C,A} \right )</math> није '''најдужи заједнички подниз''' низова <math>X</math> и <math>Y</math>. Низ <math>\left ( \text{B,C,B,A} \right )</math> је '''најдужи заједнички подниз'''<ref>Cormen, Leiserson, Rivest: Introduction to algorithms</ref> низова <math>X</math> и <math>Y</math>, као што је и низ <math>\left ( \text{B,D,A,B} \right )</math> јер низови <math>X</math> и <math>Y</math> немају зајеничких поднизова дужине 5 или веће.

Проблем '''најдужи заједнички подниз (НЗП)''' представља проналажење заједничког подниза максималне дужине унапред задатих низова <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> и <math>Y = \left \{ y_1, y_2, \dots , y_n \right \}</math>.

== Карактеризација најдужег заједничког подниза ==
У покушају да решимо '''НЗП''' проблем грубом силом, прво бисмо нумерисали све поднизове низа <math>X</math> и онда бисмо проверили да ли је сваки од њих уједно и подниз низа <math>Y</math>, памтећи најдужи који смо до тог тренутка пронашли. Сваком поднизу низа <math>X</math> одговара подскуп индекса <math>\left \{ 1, \dots ,m \right \}</math> низа <math>X</math>. Обзиром да низ <math>X</math> има <math>2^m</math> поднизова, овакав приступ захтева експоненцијално време што га чини непрактичним за дугачке низове.

'''НЗП''' проблем има својство оптималног потпроблема, што доказује следећа теорема. Природне класе потпроблема одговорају паровима ''префикса'' полазних низова. Прецизније, ако имамо низ <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> дефинишимо <math>i</math>-ти '''префикс''' од <math>X</math> за свако <math>i = 1, \dots ,m</math> као <math>X_i = \left ( x_1, \dots, x_i \right )</math>. На пример, ако је <math>X = \left ( \text {A,B,C,D,B,A,B} \right )</math> тада је <math>X_4 = \left ( \text {A,B,C,D} \right )</math> и <math>X_0</math> је празан низ.

; Теорема
Нека су дати низови <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> и <math>Y = \left \{ y_1, y_2, \dots , y_n \right \}</math>, и нека је <math>Z = \left ( z_1, \dots ,z_k \right )</math> било који најдужи заједнички подниз (НЗП) низова <math>X</math> и <math>Y</math>. Тада:
# Ако <math>x_m = y_n</math>, онда <math>z_k = x_m = y_n</math> и <math>Z_{k-1}</math> је НЗП низова <math>X_{m-1}</math> и <math>Y_{n-1}</math>.
# Ако <math>x_m \ne y_n</math>, онда <math>z_k \ne x_m</math> и <math>Z</math> је НЗП низова <math>X_{m-1}</math> и <math>Y</math>.
# Ако <math>x_m \ne y_n</math>, онда <math>z_k \ne y_n</math> и <math>Z</math> је НЗП низова <math>X</math> и <math>Y_{n-1}</math>.

; Доказ
: '''(1)''' Ako je <math>z_k \ne x_m</math> онда можемо да надовежемо <math>x_m = y_n</math> на <math>Z</math> чиме бисмо добили заједнички подниз низова <math>X</math> и <math>Y</math> дужине <math>k+1</math>, што је у контрадикцији са претпоставком да је <math>Z</math> најдужи заједнички подниз. Стога, мора да важи <math>z_k = x_m = y_n</math>. Префикс <math>Z_{k-1}</math> је заједнички подниз низова <math>X_{m-1}</math> и <math>Y_{n-1}</math> дужине <math>k-1</math>, и још остаје да се покаже да је НЗП. Претпоставимо да постоји заједнички подниз <math>W</math> низова <math>X_{m-1}</math> и <math>Y_{n-1}</math> са дужином већом од <math>k-1</math>. Тада, надовезујући <math>x_m = y_n</math> на <math>W</math> добијамо заједнички подниз дужине веће од <math>k</math>, што је у контрадикцији са претпоставком да је <math>Z</math> НЗП.
: '''(2)''' Ако <math>z_k \ne x_m</math>, онда је <math>Z</math> је заједнички подниз низова <math>X_{m-1}</math> и <math>Y</math>. Ако би постојао заједнички подниз <math>W</math> низова <math>X_{m-1}</math> и <math>Y</math> дужине веће од <math>k</math>, онда би <math>W</math> био заједнички подниз низова <math>X_m</math> и <math>Y</math>, што је у контрадикцији са претпоставком да је <math>Z</math> НЗП низова <math>X</math> и <math>Y</math>.
: '''(3)''' Симетрично другом случају.

Начин на који теорема карактерише '''најдужи заједнички подниз''' говори нам да НЗП два низа у себи садржи и НЗП префикса та два низа. Стога, прблем НЗП има својство оптималног потпроблема. 

== Рекурзивно решење ==
Теорема нам говори да треба да испитамо или једно или два потпроблема када проналазимо '''најдужи заједнички подниз''' низова <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> и <math>Y = \left \{ y_1, y_2, \dots , y_n \right \}</math>. Ако је <math>x_m = y_n</math> онда морамо да пронађемо НЗП низова <math>X_{m-1}</math> и <math>Y_{n-1}</math>. Надовезујући <math>x_m = y_n</math> на пронађени НЗП добићемо најдужи заједнички подниз низова <math>X</math> и <math>Y</math>. Ако <math>x_m \ne y_n</math>, онда морамо да решимо два потпроблема: морамо да пронађемо НЗП низова <math>X_{m-1}</math> и <math>Y</math> и НЗП низова <math>X</math> и <math>Y_{n-1}</math>. Дужи од два пронађена најмања заједничка подниза је НЗП полазних низова <math>X</math> и <math>Y</math>.

Лако се уочава да се потпроблеми проблема НЗП међусобно преплићу. Како бисмо пронашли НЗП низова <math>X</math> и <math>Y</math>, можда треба да пронађемо и најдуже заједничке поднизове низова <math>X_{m-1}</math> и <math>Y</math> и низова <math>X</math> и <math>Y_{n-1}</math>. Али, сваки од ова два потпроблема за потпроблем има проналазак најмањег заједничког подниза низова <math>X_{m-1}</math> и <math>Y_{n-1}</math>. Многи други потпроблеми деле своје потпроблеме.

Рекурзивно решење НЗП проблема обухвата и креирање рекурентне релације за проналажење оптималног решења. Дефинишимо <math>c \left [ i,j \right ]</math> као дужину НЗП низова <math>X_i</math> и <math>Y_j</math>. Ако је <math>i=0</math> или <math>j=0</math>, онда један од низова има дужину <math>0</math>, чиме је и НЗП дужине <math>0</math>. Опитимални потпроблем НЗП проблема даје следећу рекурентну релацију:
:<math>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 \ne y_j
\end{cases}</math>

Приметимо да у рекурентној релацији услов у проблему одређује који потпроблем ћемо да разматрамо. Када је <math>x_i = y_j</math>, тада треба да разматрамо потпроблем који представња тражење најдужег заједничког подниза низова <math>X_{i-1}</math> и <math>Y_{j-1}</math>. У супротном, разматраћемо два потпроблема, један је проналажење НЗП низова <math>X_{i}</math> и <math>Y_{j-1}</math> и НЗП низова <math>X_{i-1}</math> и <math>Y_{j}</math>.

== Израчунавање дужине најдужег заједничког подниза ==
Уз помоћ горе наведене рекурентне релације лако можемо да напишемо рекурзивни алгоритам који ће израчунавати дужину најдужег заједничког подниза два низа у експоненцијалном времену. Обзиром да НЗП проблем има само <math>\Theta \left ( mn \right )</math> различитих потпроблема можемо да искористимо динамичко програмирање за израчунавање решења одоздо на горе.

Процедура '''LCS_length''' као улазне аргументе има два низа <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> и <math>Y = \left \{ y_1, y_2, \dots , y_n \right \}</math>. Процедура чува вредности <math>c\left [ i , j \right ]</math> у матрици <math>c \left [ 0 \dots m, 0 \dots n \right ] </math>, тако што редом по врстама с лева на десно израчунава дужине најдужих заједничких поднизова низова <math>X_i</math> и <math>Y_j</math>. Процедура такође одржава и помоћну матрицу <math>b \left [ 1 \dots m, 1 \dots n \right ] </math> коју користимо при конструкцији најдужег заједничког подниза. Интуитивно, <math>b \left [ i , j \right ]</math> показује на запис у матрици који одговара оптималном решењу изабраног потпроблема приликом израчунавања <math>c\left [ i , j \right ]</math>. Процедура враћа матрице <math>b</math> и <math>c</math>, при чему <math>c\left [ m , n \right ]</math> садржи дужину најдужег заједничког подниза низова <math>X</math> и <math>Y</math>.

Дефинишимо следеће симболе: 

:<math> \text {GORELEVO } \nwarrow </math>
:<math> \text {GORE } \uparrow </math>
:<math> \text {LEVO } \leftarrow </math>

<source lang = "c" line = "GESHI_NORMAL_LINE_NUMBERS">
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
</source>
Време извршавања приказане процедуре је <math>\Theta \left ( mn \right )</math>, јер сваки унос у матрицу захтева <math>\Theta \left ( 1 \right )</math> корака приликом извршавања.

== Конструисање најдужег заједничког подниза ==
Матрица <math>b</math> коју враћа процедура '''LCS_length''' омогућава нам да брзо конструишемо НЗП низова <math>X = \left \{ x_1, x_2, \dots , x_m \right \}</math> и <math>Y = \left \{ y_1, y_2, \dots , y_n \right \}</math>. Једноставно кренемо од <math>b\left [ m , n \right ]</math> и само се крећемо кроз матрицу пратећи стрелице. Када год наиђемо на стрелицу <math>\nwarrow</math> на пољу <math>b \left [ i , j \right ]</math> то значи да је <math>x_i = y_j</math> елемент најдужег заједничког подниза низова <math>X</math> и <math>Y</math> који је процедура '''LCS_length''' пронашла. Овим приступом откривамо елементе НЗП низова <math>X</math> и <math>Y</math> у обрнутом поретку. Следећа рекурзивна процедура штампа елементе НЗП низова <math>X</math> и <math>Y</math> у оригиналном поретку. Позив процедуре је следећи '''LCS_print(b, X, X.dužina, Y.dužina)'''.
<source lang = "c" line = "GESHI_NORMAL_LINE_NUMBERS">
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)
</source>
Процедури '''LCS_print''' је потребно <math>\mathrm{O} \left ( m + n \right )</math> корака за извршавање, јер се у сваком рекурзивном позиву смањује барем један од индекса <math>i</math> и 
<math>j</math>.

== Унапређења ==
У НЗП алгоритму могуће је потпуно елиминисати матрицу <math>b</math>. Сваки <math>c \left [ i,j \right ]</math> зависи само од још три записа у матрици <math>c</math>: <math>c \left [ i-1,j-1 \right ]</math>,<math>c \left [ i-1,j \right ]</math> и <math>c \left [ i,j-1 \right ]</math>. Уколико имамо вредност <math>c \left [ i,j \right ]</math>, онда можемо у константном времену да утврдимо која од ове три вредности је била искоришћена приликом израчунавања <math>c \left [ i,j \right ]</math> без потребе да приступамо елементима матрице <math>b</math>. Стога можемо да реконструишемо НЗП у времену <math>\mathrm{O} \left ( m + n \right )</math>. Иако ћемо на овај начин уштедети <math>\Theta \left ( mn \right )</math> простора, додатни простор за израчунавање најдужег заједничког подниза не опада асимптотски, јер нам и даље треба <math>\Theta \left ( mn \right )</math> простора за складиштење матрице <math>c</math>.

Ипак, можемо асимптотски да смањимо потребан простор за израчунавање дужине најдужег заједничког подниза, јер су нам у сваком тренутку потребне само две врсте матрице <math>c</math>: врста која се израчунава и претходно израчуната врста. Ово унапређење је корисно само ако нам треба дужина најдужег заједничког подниза, јер смањена матрица не садржи довољно информација за реконструкцију самог НЗП-а у времену <math>\mathrm{O} \left ( m + n \right )</math>.

== Примене ==
Апликације у биологији често треба да пореде ДНК ланце два или више различитих организама. ДНК ланци могу да се представе као коначне речи над језиком <math>\mathrm{L} = \left \{ A,C,G,T \right \}</math>. Један од разлога за поређење ДНК ланаца различитих организама је утврђивање њихове међусобне сличности, што може да буде мера сродности различитих организама. Сличност два ланца може да се мери на различите начине. Један од начина како можемо да измеримо сличност два ДНК ланца <math>S_1</math> и <math>S_2</math> је да пронађемо трећи ланац <math>S_3</math> у коме се симболи из језика <math>\mathrm{L}</math> појављују и у ланцима <math>S_1</math> и <math>S_2</math>; симболи морају да се појављују у истом редоследу али не и узастопно. Што је дужи пронађени ланац <math>S_3</math>, то су ланци <math>S_1</math> и <math>S_2</math> сличнији.

== Опис решења за две ниске ==

За проналазак најдуже заједничке подниске две ниске ''x'' и ''y'', израчунавају се дужине најдужих заједничких подниски свих могућих парова префикса, једног из ниске ''x'' и другог из ниске ''y''. Нека је ''x'' = ''x''<sub>1</sub>...''x''<sub>''m''</sub> и ''y'' = ''y''<sub>1</sub>...''y''<sub>''n''</sub>. За свако ''i'' = 0,1,...,''m'' и ''j'' = 0,1,...,''n'', најдужа заједничка подниска префикса ''x''<sub>1</sub>...''x''<sub>''i''</sub> ниске ''x'' и префикса ''y''<sub>1</sub>...''y''<sub>''j''</sub> ниске ''y'' се може одредити на следећи начин. Пре свега, уколико је ''i'' или ''j'' једнако 0, тада један од ових префикса мора бити празна реч, па је једина могућа заједничка подниска таква два префикса празна реч.

Уколико су ''i'' и ''j'' оба већи од 0, посматрају се два случаја у зависности од тога да ли су последњи знакови две ниске једнаки:
# Ако је ''x<sub>i</sub>'' ≠ ''y<sub>j</sub>'', тада најдужа заједничка подниска два префикса не може укључити ''x<sub>i</sub>'' и ''y<sub>j</sub>'', већ је она једнака дужој од две најдуже заједничке подниске - за префиксе ''x''<sub>1</sub>...''x''<sub>''i''-1</sub> и ''y''<sub>1</sub>...''y<sub>j</sub>'', односно ''x''<sub>1</sub>...''x''<sub>''i''</sub> и ''y''<sub>1</sub>...''y''<sub>''j''-1</sub>.
# Ако је ''x<sub>i</sub>'' = ''y<sub>j</sub>'', тада најдужа заједничка подниска може укључити ''x<sub>i</sub>'' и ''y<sub>j</sub>'', који неће реметити друга потенцијална везивања симбола у два префикса. То значи да је најдужа заједничка подниска за префиксе ''x''<sub>1</sub>...''x''<sub>''i''</sub> и ''y''<sub>1</sub>...''y''<sub>''j''</sub> заправо најдужа заједничка подниска за префиксе ''x''<sub>1</sub>...''x''<sub>''i''-1</sub> и ''y''<sub>1</sub>...''y''<sub>''j''-1</sub> на које је надовезан последњи симбол који је исти у два префикса - ''x<sub>i</sub>'', односно ''y<sub>j</sub>''.

На основу ових запажања може се извести рекурзивна дефиниција за дужину најдуже заједничке подниске префикса ''x''<sub>1</sub>...''x<sub>i</sub>'' и ''y''<sub>1</sub>...''y<sub>j</sub>''. Ако ту дужину означимо са ''L''(''i'',''j''), тада је:

:<math>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.</math>

Дужина најдуже заједничке подниске за две целе ниске ''x'' и ''y'' је ''L''(''m'',''n''), што се може израчунати једноставним [[Рекурзија|рекурзивним]] алгоритмом на основу претходне формуле. Међутим, време извршавања таквог алгоритма би било [[Експоненцијално време|експоненцијално]], а разлог за то је чињеница да алгоритам више пута рачуна дужину најдуже заједничке подниске за исте парове префикса.

Рекурзивни алгоритам се може знатно убрзати ако се примени приступ [[Динамичко програмирање|динамичког програмирања]] и конструише табела ''L'' вредности дужина ''L''(''i'',''j'') за ''i''=0,1,...,''m'' и ''j''=0,1,...,''n''. Пошто у израчунавању дужине L(''i'',''j'') учествују вредности L(''i'',''j''-1), L(''i''-1,''j'') и L(''i''-1,''j''-1), табела се може попуњавати ред по ред и тако обезбедити да се потребне вредности за L(''i'',''j'') налазе у табели. Ово је илустровано на следећој слици:
{|{{table}}
| ''L''(''i''-1,''j''-1)
| ''L''(''i''-1,''j'')
|- 
| ''L''(''i'',''j''-1)
| '''''L''(''i'',''j'')'''
|}

Табела ''L'' се може искористити за одређивање симбола који чине најдужу заједничку подниску. Пошто табела ''L'' садржи дужине најдужих заједничких подниски свих парова префикса две дате ниске, од доњег десног угла табеле се може формирати пут кроз ову табелу и на том путу узимати одређени симболи. Тако одабрани симболи у обрнутом редоследу представљају најдужу заједничку подниску за две дате ниске. Ако претпоставимо да на путу од доњег десног угла табеле ''L'' долазимо до тачке пресека ''i''-те врсте и ''j''-те колоне која одговара пару знакова ''x<sub>i</sub>'' и ''y<sub>j</sub>''. Ако је ''x<sub>i</sub>''=''y<sub>j</sub>'', онда знакове ''x<sub>i</sub>'' и ''y<sub>j</sub>'' сматрамо упареним и знак ''x<sub>i</sub>''=''y<sub>j</sub>'' додајемо испред свих знакова најдуже заједничке подниске који су до тада нађени. На путу у наредном кораку се прелази дијагонално лево на горњи ред, тј. у ред ''i''-1 и колону ''j''-1. Ако је ''x<sub>i</sub>''≠''y<sub>j</sub>'', вредност ''L''(''i'',''j'') мора бити једнака једној од дужина ''L''(''i''-1,''j'') или ''L''(''i'',''j''-1) (или обема). У првом случају, потребно је прећи на позицију (''i''-1,''j''), а у другом случају на позицију (''i'',''j''-1). У случају једнаких вредности, на произвољан начин се бира једна од две позиције.

=== Пример ===

На слици је приказан резултат верзије алгоритма која користи динамичко програмирање за ниске ''"бтматмац"'' и ''"мтамтаб"''. Вредности у матрици које су означене жутом бојом представљају пут којим се одређује најдужа заједничка подниска, па је једно од могућих решења за овај пример подниска ''"мата"''.

{|{{table}}
|
| 
| 
| б
| т
| '''м'''
| '''а'''
| '''т'''
| м
| '''а'''
| ц
|- 
|
| '''j\i'''
| '''0'''
| '''1'''
| '''2'''
| '''3'''
| '''4'''
| '''5'''
| '''6'''
| '''7'''
| '''8'''
|-
|
| '''0'''
| 0
| 0
| style="background:yellow"|0
| 0
| 0
| 0
| 0
| 0
| 0
|-
| '''м'''
| '''1'''
| 0
| 0
| 0
| style="background:yellow"|1
| 1
| 1
| 1
| 1
| 1
|-
| т
| '''2'''
| 0
| 0
| 1
| style="background:yellow"|1
| 1
| 2
| 2
| 2
| 2
|-
| '''а'''
| '''3'''
| 0
| 0
| 1
| 1
| style="background:yellow"|2
| 2
| 3
| 3
| 3
|-
| м
| '''4'''
| 0
| 0
| 1
| 2
| style="background:yellow"|2
| 2
| 3
| 3
| 3
|-
| '''т'''
| '''5'''
| 0
| 0
| 1
| 2
| 2
| style="background:yellow"|3
| style="background:yellow"|3
| 3
| 3
|-
| '''а'''
| '''6'''
| 0
| 0
| 1
| 2
| 3
| 3
| 3
| style="background:yellow"|4
| style="background:yellow"|4
|-
| б
| '''7'''
| 0
| 1
| 1
| 2
| 3
| 3
| 3
| 4
|style="background:yellow"| 4
|}

== Имплементација алгоритма у програмском језику Јава ==

=== Рекурзивни алгоритам ===

<source lang="Java">

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

</source>

=== Алгоритам заснован на динамичком програмирању ===

<source lang="Java">

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();
}
</source>

== Имплементација алгоритма у програмском језику C ==
Имплементација је у програмском језику C уз претпоставку о максималној дужини низова и уз претпоставку да се ради о низовима који садрже целобројне вредности.

<source lang = "c" line = "GESHI_NORMAL_LINE_NUMBERS">
#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);    
}
</source>

== Сложеност алгоритама ==

Рекурзивни алгоритам којим се одређује најдужа заједничка подниска две ниске има експоненцијалну сложеност. Ако две ниске, за које је потребно одредити најдужу заједничку подниску, имају дужине ''m'', односно ''n'' и нека је ''k'' = ''m'' + ''n'', време извршавања таквог алгоритма је θ(2<sup>''k''</sup>).

Сложеност алгоритма заснованом на динамичком програмирању за одређивање најдуже заједничке подниске две ниске износи Ο(''mn'').

== Референце ==
{{reflist}}

== Литература ==
{{refbegin}}
* {{Cite book|ref= harv|author=Дејан Живковић, |title=Основе дизајна и анализе алгоритама|location=|publisher=ЦЕТ|year=2007|isbn=978-86-7991-327-2|pages=}} Поглавље 7.
{{refend}}

== Спољашње везе ==
* [http://rosettacode.org/wiki/Longest_common_subsequence Имплементација алгоритма за одређивање најдуже заједничке подниске у многим програмским језицима]
* -{[https://xlinux.nist.gov/dads/HTML/longestCommonSubsequence.html Dictionary of Algorithms and Data Structures: longest common subsequence]}-
* -{[http://www.codingalpha.com/longest-common-subsequence-c-program/ Implementation of Longest Common Subsequence Algorithm in C Programming Language]}-

[[Категорија:Алгоритми на нискама]]