სამი სტრიქონის LCS (გრძელი საერთო შედეგი)


Რთული ტური Hard
ხშირად ეკითხებიან Amazon CodeNation Expedia Google Uber Zoho
დინამიური პროგრამირება სიმებიანი

პრობლემა "სამი სტრიქონის LCS (გრძელი საერთო შედეგი)" აღნიშნავს, რომ თქვენ გეძლევათ 3 სტრიქონი. შეიტყვეთ ამ 3 სტრიქონის გრძელი საერთო მიმდევრობა. LCS არის სიმებიანი, რომელიც საერთოა 3 სტრიქონს შორის და შედგება სიმბოლოებისგან, რომლებსაც აქვთ ერთი და იგივე რიგი, მოცემულ 3 სტრიქონში.

მაგალითი

სამი სტრიქონის LCS (გრძელი საერთო შედეგი)

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

მიდგომა

პრობლემა შეყვანის სახით გვაძლევს 3 სტრიქონს და ვთხოვთ იპოვოთ მათგან გრძელი საერთო თანმიმდევრობა. თანმიმდევრობა არის სტრიქონი, რომელიც რჩება ორიგინალური სიმების სიმბოლოების წაშლისას. ამრიგად, მოცემულ 3 სტრიქონში უნდა ვიპოვოთ საერთო თანმიმდევრობა, რომელსაც აქვს მაქსიმალური სიგრძე.

გულუბრყვილო მიდგომა პრობლემისადმი საკმაოდ ჰგავს ნორმალური გრძელი საერთო შედეგიდან გამომდინარე პრობლემას. ჩვენ უკვე განვიხილეთ LongestCommon თანმდევი პრობლემის პრობლემა. მაგრამ ჩვენ ასევე განვიხილეთ, რომ გულუბრყვილო მიდგომა არ არის საკმარისად ეფექტური პრობლემის გადაჭრის ვადებში. ასე რომ, პრობლემის გადაჭრა ვადის გადაჭარბების გარეშე. ჩვენ გამოვიყენებთ დინამიური პროგრამირება კითხვის გადასაჭრელად. მდგომარეობა მსგავსი იქნება LCS– ის მდგომარეობისა 2 სტრიქონისთვის. აქ გვექნება 3 მდგომარეობა, რომლებიც ეხება ინდექსებს 3 შესაბამის სტრიქონში. ასე რომ, ჩვენი dp მასივი იქნება 3D მასივი, სადაც ჩვენ ვინახავთ 0-ს, თუ რომელიმე ინდექსში 3 მათგანია 0. თუ სამივე ინდექსის სიმბოლოა, მაშინ ქვეპრობლემის პასუხს ვმატებთ 3-ს (ქვესადგურების LCS სიგრძე 1-დან 0-ით ნაკლები თითოეულ ინდექსზე). თუ ორი სტრიქონიდან რომელიმე არ არის ერთი და იგივე ხასიათი, ჩვენ ვინახავთ ქვეპროგრამების მაქსიმუმს, სადაც თითოეული ინდექსის სათითაოდ შემცირება ხდება.

კოდი

C ++ კოდი 3 სიმების LCS მოსაძებნად

#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

ჯავის კოდი 3 სიმების LCS მოსაძებნად

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), იმიტომ, რომ ჩვენ უნდა გადავკვეთოთ სიგრძის მქონე სამივე სტრიქონი N, Mდა K. გამოყენების გამო დინამიური პროგრამირება ჩვენ შეგვიძლია შევამციროთ ექსპონენციალური დროის სირთულე პოლინომამდე.

სივრცის სირთულე

O (N * M * K), რადგან ჩვენ უნდა შევქმნათ 3D DP მასივი შედეგის შესანახად უფრო მცირე ქვეპროგრამისთვის და შემდეგ გავაერთიანოთ შედეგი, რომ მივიღოთ თავდაპირველი პრობლემის პასუხი. ამრიგად, სამი სტრიქონის LCS (გრძელი საერთო შედეგი) პოვნა მრავალწევრის სივრცის სირთულეს წარმოადგენს.