ЛЦС (најдужа уобичајена след) од три низа  


Ниво тешкоће Тежак
Често питани у амазонка ЦодеНатион Екпедиа гоогле Убер Зохо
Динамичко програмирање низ

Проблем „ЛЦС (најдужа заједничка след) од три низа“ наводи да су вам дата 3 низа. Откријте најдужу заједничку подредност ових 3 низа. ЛЦС је низ који је уобичајен међу 3 низа и састоји се од знакова који имају исти редослед у све 3 задате жице.

Пример  

ЛЦС (најдужа уобичајена след) од три низаПин

"gxtxayb" 
"abgtab" 
"gyaytahjb"
Length of LCS: 4("gtab")

Приступ  

Проблем нам даје 3 низа као улаз и затражено је да пронађемо најдужу заједничку подредност од њих. Подсеквенца је низ који остаје када из оригиналног низа избришемо неке знакове. Стога морамо да пронађемо заједничку подред у дата 3 низа која има максималну дужину.

Наивни приступ проблему је прилично сличан приступу нормалног проблема са најдужим заједничким последицама. Већ смо разговарали о проблему са најдужим заједничким последицама. Али такође смо разговарали о томе да наивни приступ није довољно ефикасан за решавање проблема у временским ограничењима. Дакле, да бисте решили проблем без прекорачења временског ограничења. Користићемо динамичко програмирање за решавање питања. Услов ће бити сличан ономе за ЛЦС за 2 жице. Овде ћемо имати 3 стања која ће се позивати на индексе у 3 одговарајућа низа. Дакле, наш дп низ ће бити 3Д низ, где чувамо 0 ако је било који од индекса међу њих 3 0. Ако је знак на сва 3 индекса онда додамо 1 одговору за потпроблем (ЛЦС поднизова из дужине 0 до 1 мање од сваког од индекса). Ако било који од два низа нема исти карактер, чувамо максимум потпроблема где се сваки индекс декрементира један по један.

Види такође
Производи опсега у низу

код  

Ц ++ код за проналажење ЛЦС-а од 3 низа

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  string x = "gxtxayb"; 
  string y = "abgtab"; 
  string z = "gyaytahjb"; 
  int n = x.length(), m = y.length(), l = z.length();
  
  int dp[n][m][l];
  memset(dp, 0, sizeof dp);
  for (int i=0; i<n; i++){ 
    for (int j=0; j<m; j++){ 
      for (int k=0; k<l; k++){
        if (x[i] == y[j] && x[i] == z[k])
          dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
        else
          dp[i][j][k] = max({i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0, k>0 ? dp[i][j][k-1] : 0}); 
      } 
    } 
  } 
  cout<<dp[n-1][m-1][l-1];
  return 0; 
}
4

Јава код за проналажење ЛЦС-а од 3 низа

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String x = "gxtxayb"; 
    String y = "abgtab"; 
    String z = "gyaytahjb"; 
    int n = x.length(), m = y.length(), l = z.length();
    
    int dp[][][] = new int[n][m][l];
    for (int i=0; i<n; i++){ 
      for (int j=0; j<m; j++){ 
        for (int k=0; k<l; k++){
          dp[i][j][k] = 0;
          if (x.charAt(i) == y.charAt(j) && x.charAt(i) == z.charAt(k))
            dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
          else
            dp[i][j][k] = Math.max(Math.max(i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0), k>0 ? dp[i][j][k-1] : 0); 
        } 
      } 
    } 
    System.out.println(dp[n-1][m-1][l-1]);
  }
}
4

Анализа сложености  

Сложеност времена

О (Н * М * К), јер морамо прећи све 3 жице дужине N, M, и K. Због употребе Динамичко програмирање способни смо да експоненцијалну временску сложеност смањимо на полином.

Сложеност простора

О (Н * М * К), јер морамо створити 3Д ДП низ за чување резултата за мањи подпроблем, а затим комбиновање резултата да бисмо добили одговор на почетни проблем. Стога проналажење ЛЦС (најдуже заједничке последице) три низа има полиномску сложеност простора.