LCS (أطول نتيجة شائعة) من ثلاثة سلاسل


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون CodeNation اكسبيديا جوجل اوبر زوهو
البرمجة الديناميكية خيط

توضح مشكلة "LCS (أطول نتيجة شائعة) المكونة من ثلاثة سلاسل" أنك تحصل على 3 سلاسل. اكتشف أطول نتيجة شائعة لهذه السلاسل الثلاثة. LCS هي السلسلة الشائعة بين السلاسل الثلاثة وتتكون من أحرف لها نفس الترتيب في كل السلاسل الثلاثة المحددة.

مثال

LCS (أطول نتيجة شائعة) من ثلاثة سلاسل

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

الرسالة

تعطينا المسألة 3 سلاسل كمدخلات ويطلب منا إيجاد أطول سلسلة متتالية مشتركة من هذه السلاسل. اللاحقة هي سلسلة يتم تركها عندما نحذف بعض الأحرف من السلسلة الأصلية. وبالتالي نحن بحاجة إلى إيجاد النتيجة المشتركة اللاحقة في السلاسل الثلاثة المعطاة والتي لها أقصى طول.

النهج الساذج للمشكلة يشبه إلى حد بعيد تلك الخاصة بمشكلة العواقب الأطول الشائعة. لقد ناقشنا بالفعل مشكلة التتابع الأطول شيوعًا. لكننا ناقشنا أيضًا أن النهج الساذج ليس فعالًا بما يكفي لحل المشكلة ضمن الحدود الزمنية. لذا ، لحل المشكلة دون تجاوز الحد الزمني. سوف نستخدم البرمجة الديناميكية لحل السؤال. ستكون الحالة مشابهة لتلك الخاصة بـ LCS لسلسلتين. هنا سيكون لدينا 2 حالات تشير إلى المؤشرات في السلاسل الثلاثة المقابلة. لذا ستكون مصفوفة dp الخاصة بنا عبارة عن مصفوفة ثلاثية الأبعاد ، حيث نقوم بتخزين 3 إذا كان أي من المؤشرات من بين 3 منها يساوي 3. إذا كان الحرف في جميع المؤشرات الثلاثة ، فإننا نضيف 0 إلى إجابة المشكلة الفرعية (LCS للسلاسل الفرعية من الطول من 3 إلى 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

كود جافا للعثور على 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

تحليل التعقيد

تعقيد الوقت

يا (N * M * K) ، لأنه يتعين علينا اجتياز جميع السلاسل الثلاثة ذات الطول N, Mو K. بسبب استخدام ملفات البرمجة الديناميكية نحن قادرون على تقليل التعقيد الزمني الأسي إلى كثير الحدود.

تعقيد الفضاء

يا (N * M * K) ، لأنه يتعين علينا إنشاء مصفوفة DP ثلاثية الأبعاد لتخزين النتيجة لمشكلة فرعية أصغر ثم دمج النتيجة للحصول على إجابة المشكلة الأولية. وبالتالي ، فإن العثور على LCS (أطول نتيجة شائعة) لثلاثة سلاسل له تعقيد مساحة متعدد الحدود.