LCS (самая длинная общая подпоследовательность) из трех строк


Сложный уровень Жесткий
Часто спрашивают в Амазонка CodeNation Expedia Google Uber Zoho
Динамическое программирование строка

Задача «LCS (самая длинная общая подпоследовательность) из трех строк» ​​утверждает, что вам даны 3 строки. Найдите самую длинную общую подпоследовательность из этих трех строк. LCS - это строка, которая является общей для трех строк и состоит из символов, имеющих одинаковый порядок во всех трех данных строках.

Пример

LCS (самая длинная общая подпоследовательность) из трех строк

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

Подход

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

Наивный подход к проблеме очень похож на подход к обычной проблеме самой длинной общей подпоследовательности. Мы уже обсуждали проблему LongestCommon Subsequence. Но мы также обсудили, что наивный подход недостаточно эффективен для решения проблемы в сжатые сроки. Итак, решить проблему, не превысив установленный срок. Мы будем использовать динамическое программирование для решения вопроса. Условие будет таким же, как у LCS для 2-х струн. Здесь у нас будет 3 состояния, которые будут ссылаться на индексы в 3 соответствующих строках. Таким образом, наш массив dp будет трехмерным массивом, в котором мы сохраняем 3, если любой из индексов среди трех из них равен 0. Если символ во всех трех индексах равен, то мы добавляем 3 к ответу на подзадачу (LCS подстрок из длина от 0 до 3 меньше, чем каждый из индексов). Если какая-либо из двух строк не имеет одного и того же символа, мы сохраняем максимум подзадач, где уменьшаем каждый индекс один за другим.

Код:

Код 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. Из-за использования Динамическое программирование мы можем уменьшить экспоненциальную временную сложность до полиномиальной.

Космическая сложность

О (Н * М * К), потому что нам нужно создать 3D-массив DP для хранения результата для меньшей подзадачи, а затем объединить результат, чтобы получить ответ для исходной проблемы. Таким образом, поиск LCS (самой длинной общей подпоследовательности) трех строк имеет сложность в полиномиальном пространстве.