ايل سي ايس (ٽن کان وڏي عرصي واري عام تعميري)


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon ڪوڊشن Expedia گوگل سليمان وساڻ زو
متحرڪ پروگرامنگ اسٽرنگ

مسئلو ٽي اسٽرنگز جو “ايل سي ايس (ڊگهي عام عهديدار)” بيان ڪيو ويو آهي ته توهان کي 3 اسٽرنگز ڏنيون ويون آهن. ان 3 اسٽرنگز جو سڀني کان ڊگهو عام نتيجو ڳوليو. ايل سي ايس جو اهو تار آهي جيڪو 3 تارن ۾ عام آهي ۽ سڀني جي ڏنل 3 وارين شين ۾ هڪ ئي حڪم اکرن وارو ٺهيل آهي.

مثال

ايل سي ايس (ٽن کان وڏي عرصي واري عام تعميري)

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

چرچو

مسئلو اسان کي 3 اسٽرنگز کي انپٽ جي طور تي ڏئي ٿو ۽ هنن کان تمام ڊگهو عام نتيجو ڳولڻ جي لاءِ چيو. ھڪڙو شروعات ھڪڙي تار آھي جيڪو ڇڏي ويو آھي جڏھن اسين ڪجھ اکرن کي اصل تار مان حذف ڪريون ٿا. تنهنڪري اسان کي ڏنل 3 تار ۾ عام تعين ڳولڻ جي ضرورت آهي جنهن جي وڌ ۾ وڌ ڊيگهه آهي.

مسئلي جو naive انداز عام طور تي تمام ويجهڙائي واري عام مسئلي جي ساڳئي طرح آهي. اسان اڳ ۾ ئي ڊگهي ڪمن جي بعد واري مسئلي تي بحث ڪيو هو. پر اسان اهو به بحث ڪيو ته وقت جي حدن هيٺ مسئلو حل ڪرڻ لاءِ نرالي انداز ڪافي ڪارائتو ناهي. تنهن ڪري ، وقت جي حد کان وڌي بغير مسئلو حل ڪرڻ جي. اسان استعمال ڪنداسين متحرڪ پروگرامنگ سوال حل ڪرڻ لاءِ. حالت 2 تارن لاءِ ايل سي ايس سان ساڳي ٿي ويندي. هتي اسان وٽ 3 رياستون آهن جيڪي 3 ساڳئي ترتيب ۾ اشارن جي حوالي ڪنديون. تنهن ڪري اسان جي ڊي پي ترتيب هڪ 3D صف ٿي ويندي ، جتي اسان 0 کي ذخيرو ڪريون ٿا جيڪڏهن انهن مان 3 وارن مان ڪنهن ۾ به 0 آهي. ڊيگهه ـ هر هڪ انڊيڪس مان گھٽ 3 کان 1 تائين. جيڪڏهن ٻن تارن مان ڪو ساڳيو ئي ڪردار نه آهي ته اسان وڌيڪ ذيلي منصوبن کي ذخيرو ڪريون ٿا جتي انڊيڪس جي هر هڪ کي ترتيب ڏين.

ڪوڊ

سي ++ ڪوڊ 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

جاوا ڪوڊ 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. استعمال جي ڪري متحرڪ پروگرامنگ اسان پولينيومائل تائين غير معمولي وقت جي پيچيدگي کي گهٽائڻ جي قابل آهيون.

خلائي پيچيدگي

اي (اين * ايم * ڪي) ، ڇاڪاڻ ته اسان کي نن subن ذيلي مسئلن جو نتيجو اسٽور ڪرڻ جي لاءِ 3 ڊي ڊي پي آر ٺاهڻي آهي ۽ پوءِ گڏيل مسئلي جي جواب کي حاصل ڪرڻ لاءِ نتيجو گڏ ڪرڻ. اھڙي طرح ٽن تارن جو ايل سي ايس (ڊگھي عام تعاقب) ڳولڻ پولي ڪوليائي خلائي پيچيدگي رکي ٿو.