LCS (најдолга заедничка последица) од три жици


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

Проблемот „LCS (најдолга заедничка последица) од три жици“ вели дека ви се дадени 3 жици. Откријте ја најдолгата заедничка сукцесија од овие 3 жици. LCS е низата што е вообичаена меѓу 3-те жици и е направена од карактери кои имаат ист редослед во сите 3 дадени жици.

пример

LCS (најдолга заедничка последица) од три жици

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

Пристап

Проблемот ни дава 3 жици како влез и побара од нив да ја најдеме најдолгата заедничка подред. Подредка е низа што останува кога ќе избришеме некои од ликовите од оригиналната низа. Така, треба да ја пронајдеме заедничката сукцесија во дадените 3 жици која има максимална должина.

Наивниот пристап кон проблемот е прилично сличен на оној на нормалниот проблем со најдолга заедничка последица. Ние веќе разговаравме за проблемот со најдолгата заедничка последица. Но, исто така разговаравме дека наивниот пристап не е доволно ефикасен за да се реши проблемот под временските ограничувања. Значи, да се реши проблемот без да се надмине временскиот рок. Ние ќе користиме динамично програмирање за решавање на прашањето. Состојбата ќе биде слична на состојбата на LCS за 2 жици. Тука ќе имаме 3 состојби кои ќе се однесуваат на индексите во 3-те соодветни низи. Значи, нашата низа dp ќе биде 3Д-низа, каде што зачувуваме 0 ако некој од индексите меѓу 3 од нив е 0. Ако карактерот е на сите 3 индекси, тогаш додаваме 1 на одговорот за подпроблемот (LCS на поднаречи од должина од 0 до 1 помалку од секој од индексите). Ако која било од двете жици нема ист карактер, тогаш ги зачувуваме максимумот на подпроблемите каде што секој од индексот се намалува еден по еден.

Код

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

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

Временска комплексност

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

Комплексноста на просторот

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