LCS (Longest Common Aftersequence) з трох радкоў


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка CodeNation Expedia Google Uber Zoho
Дынамічнае праграмаванне Радок

Праблема «LCS (Longest Common Undersequence) з трох радкоў» абвяшчае, што вам дадзена 3 радкі. Даведайцеся, якая самая доўгая агульная падпаслядка гэтых 3 радкоў. LCS - гэта радок, які распаўсюджаны сярод 3 радкоў і складаецца з сімвалаў, якія маюць аднолькавы парадак ва ўсіх 3 дадзеных радках.

Прыклад

LCS (Longest Common Aftersequence) з трох радкоў

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

Падыход

Праблема дае нам 3 радкі як увод і просіць знайсці самую доўгую агульную паслядоўнасць з іх. Паслядоўнасць - гэта радок, які застаецца, калі мы выдаляем некаторыя сімвалы з зыходнага радка. Такім чынам, нам трэба знайсці агульную паслядоўнасць у дадзеных 3 радках, якая мае максімальную даўжыню.

Наіўны падыход да праблемы цалкам падобны на падыход да нармальнай праблемы з самай доўгай агульнай паслядоўнасцю. Мы ўжо абмяркоўвалі праблему LongestCommon Subsequence. Але мы таксама абмеркавалі, што наіўны падыход недастаткова эфектыўны для вырашэння праблемы ва ўстаноўленыя тэрміны. Такім чынам, каб вырашыць праблему без перавышэння тэрміну. Мы будзем выкарыстоўваць дынамічнае праграмаванне для вырашэння пытання. Умова будзе аналагічная LCS для 2 радкоў. Тут мы будзем мець 3 стану, якія будуць спасылацца на індэксы ў 3 адпаведных радках. Такім чынам, наш масіў dp будзе 3D-масівам, дзе мы захоўваем 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

Аналіз складанасці

Складанасць часу

O (N * M * K), таму што мы павінны прайсці ўсе 3 радкі, якія маюць даўжыню N, M, і K. З-за выкарыстання Дынамічнае праграмаванне мы можам звесці экспаненцыяльную складанасць часу да мнагачлена.

Касмічная складанасць

O (N * M * K), таму што мы павінны стварыць масіў 3D DP для захоўвання выніку для меншай падзадачы, а затым аб'яднання выніку для атрымання адказу на першапачатковую задачу. Такім чынам, знаходжанне LCS (найдаўжэйшай агульнай паслядоўнасці) трох радкоў мае шматпрофільную складанасць прасторы.