LCS (Найдовша загальна послідовність) з трьох рядків  


Рівень складності Жорсткий
Часто запитують у Амазонка CodeNation Expedia Google Убер 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 до відповіді на підзадачу (LCS підрядків з довжина на 1 до 0 менше, ніж кожен з індексів). Якщо будь-яка з двох рядків не має однакового символу, тоді ми зберігаємо максимум підзадач, де зменшуємо кожен індекс по одному.

Дивись також
Добутки діапазонів у масиві

код  

Код С ++ для пошуку 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 (Найдовша загальна послідовність) трьох рядків має складність простору поліномів.