LCS (Longest Common Subsequence) от три низа


Ниво на трудност Трудно
Често задавани в Амазонка CodeNation Expedia Google Uber Zoho
Динамично програмиране Низ

Проблемът „LCS (най-дългата обща последователност) от три низа“ гласи, че са ви дадени 3 низа. Открийте най-дългата обща подпоследователност на тези 3 низа. LCS е низът, който е често срещан сред 3-те низа и е съставен от символи, имащи еднакъв ред във всичките 3 дадени низа.

Пример

LCS (Longest Common Subsequence) от три низа

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

Подход

Проблемът ни дава 3 низа като вход и иска да намерим най-дългата обща подпоследователност от тях. Подпоследователността е низ, който остава, когато изтрием някои от символите от оригиналния низ. По този начин трябва да намерим общата подпоследователност в дадените 3 низа, която има максималната дължина.

Наивният подход към проблема е доста подобен на този на нормалния проблем с най-дългата обща последователност. Вече бяхме обсъждали проблема с най-общата последователност. Но също така обсъдихме, че наивният подход не е достатъчно ефективен, за да разреши проблема в рамките на сроковете. Така че, за да разрешите проблема, без да превишавате срока. Ние ще използваме динамично програмиране за решаване на въпроса. Условието ще бъде подобно на това на LCS за 2 низа. Тук ще имаме 3 състояния, които ще се отнасят до индексите в 3-те съответни низа. Така че нашият dp масив ще бъде 3D масив, където съхраняваме 0, ако някой от индексите сред трите от тях е 3. Ако знакът на всичките 0 индекса е, добавяме 3 към отговора за подпроблемата (LCS на поднизовете от дължина 1 до 0 по-малка от всеки от индексите). Ако някой от двата низа няма един и същ знак, тогава ние съхраняваме максимума от подпроблемите, където декрементираме всеки от индекса един по един.

код

C ++ код за намиране на LCS от 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

Java код за намиране на LCS от 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

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

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

O (N * M * K), защото трябва да пресечем всичките 3 низа с дължина N, M, и K. Заради използването Динамично програмиране ние сме в състояние да намалим експоненциалната времева сложност до полином.

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

O (N * M * K), защото трябва да създадем 3D DP масив за съхраняване на резултата за по-малка подпроблема и след това комбиниране на резултата, за да получим отговора за първоначалния проблем. По този начин намирането на LCS (Longest Common Subsequence) на три низа има полиномна сложност на пространството.