သုံးကြိုး၏ LCS (အရှည်ဆုံးအဖြစ်များသည့်နောက်ဆက်တွဲ)


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ CodeNation Expedia Google Uber Zoho
Dynamic Programming ကြိုး

“ ကြိုးသုံးချောင်း၏ LCS (အရှည်ဆုံးအဖြစ်များဆုံးနောက်ဆက်တွဲ)” ပြproblemနာကသင့်အားကြိုး ၃ ခုပေးထားသည်ဟုဖော်ပြသည်။ ဒီကြိုး ၃ ခုရဲ့အရှည်ဆုံးဘုံနောက်ဆက်တွဲကိုရှာပါ။ LCS သည် string ၃ ခုကြားတွင်တွေ့ရလေ့ရှိပြီးပေးထားသော string ၃ ခုလုံးတွင်တူညီသောအစဉ်လိုက်ရှိသည့်ဇာတ်ကောင်များဖြင့်ပြုလုပ်ထားသည်။

နမူနာ

သုံးကြိုး၏ LCS (အရှည်ဆုံးအဖြစ်များသည့်နောက်ဆက်တွဲ)

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

ချဉ်းကပ်နည်း

ပြနာကကျွန်တော်တို့ကိုကြိုး ၃ ခုပေးပြီး ၄ င်းတို့ထဲကအရှည်ဆုံးဘုံနောက်ဆက်တွဲကိုရှာဖို့တောင်းဆိုခဲ့တယ်။ နောက်ဆက်တွဲဆိုသည်မှာ string တစ်ခုမှစာအချို့ကိုကျွန်ုပ်တို့ဖျက်ပစ်သောအခါကျန်ကြွင်းသောစာကြောင်းဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်အများဆုံးအရှည်ရှိသည့်ပေးထားသော 3 strings တွင်ဘုံနောက်ဆက်တွဲကိုရှာရန်လိုအပ်သည်။

ပြtheနာအပေါ်နုံချဉ်းကပ်နည်းသည်ပုံမှန်အရှည်ဆုံးအဖြစ်များသည့်နောက်ဆက်တွဲပြproblemနာနှင့်ဆင်တူသည်။ ကျွန်ုပ်တို့သည် LongestCommon နောက်ဆက်တွဲပြproblemနာကိုဆွေးနွေးထားပြီးဖြစ်သည်။ သို့သော်နုံချဉ်းကပ်မှုသည်ပြlimitsနာကိုအချိန်ကာလတစ်ခုအတွင်းဖြေရှင်းနိုင်လောက်အောင်ထိရောက်မှုမရှိကြောင်းကျွန်ုပ်တို့လည်းဆွေးနွေးခဲ့သည်။ ဒါကြောင့်ပြlimitနာကိုအချိန်ကန့်သတ်ချက်ထက်မပိုဘဲဖြေရှင်းရန်။ ငါတို့သုံးမယ် dynamic programming ကို မေးခွန်းဖြေရှင်းဘို့။ အခြေအနေ ၂ ကြိုးအတွက် LCS နှင့်တူလိမ့်မည်။ ဤနေရာတွင်သက်ဆိုင်ရာ string ၃ ခုရှိညွှန်းကိန်းများကိုရည်ညွှန်းမည့်ပြည်နယ် ၃ ခုရှိသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့၏ dp ခင်းကျင်းမှုသည် 2D ခင်းကျင်းမှုဖြစ်လိမ့်မည်။ ၎င်းတို့အနက် ၃ ခုအနက်မည်သည့်အညွှန်းကိန်းသုညသုညသိုလှောင်သည်ကို 3 ထားရမည်။ အကယ်၍ ညွှန်းကိန်း ၃ ခုစလုံးရှိအက္ခရာများဖြစ်ပါက subproblem (LCS မှ substrings ၏ LCS) အတွက်အဖြေတစ်ခုထပ်ထည့်သည်။ ညွှန်းကိန်းအသီးအသီးထက်လျော့နည်း 3 မှ 3 အရှည်) ။ Strings ၂ ခုထဲမှမည်သည့် character မျှတူညီခြင်းမရှိပါကကျွန်ုပ်တို့သည် subproblems အများဆုံးကို index တစ်ခုချင်းစီကိုတ ဦး ချင်းစီလျော့ကျအောင်အများဆုံးသိုလှောင်သည်။

ကုဒ်

C ++ ကုဒ်နံပါတ် (၃) ခု၏ 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

LCS 3 strings ကိုရှာရန် Java code

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။ အသုံးပြုသောကြောင့် Dynamic Programming ကျနော်တို့ polynomial ဖို့အဆအချိန်ရှုပ်ထွေးမှုကိုလျှော့ချနိုင်ကြသည်။

အာကာသရှုပ်ထွေးမှု

အို (N * M * K) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာသေးငယ်သော subproblem အတွက်ရလဒ်သိုလှောင်ပြီးတော့ကန ဦး ပြproblemနာအတွက်အဖြေရရှိရန်ရလဒ်ကိုပေါင်းစပ်ရန်အတွက် 3D DP ခင်းကျင်းမှုတစ်ခုကိုဖန်တီးရမယ်။ ထို့ကြောင့်သုံးကြိုး၏ LCS (အရှည်ဆုံးအဖြစ်များသည့်နောက်ဆက်တွဲ) ကိုရှာဖွေခြင်းတွင် polynomial space ရှုပ်ထွေးသည်။