সাধারণ সুপার সিকোয়েন্স (Shortest Common Super Sequence)

সাধারণ সুপার সিকোয়েন্স হল এমন একটি ক্রম যেখানে প্রদত্ত দুটি সিকোয়েন্সের প্রতিটি উপাদান উপস্থিত থাকে। সহজ কথায়, দেওয়া দুটি স্ট্রিং উভয়ই সর্বনিম্ন সাধারণ সুপার-সিকোয়েন্সের উপ-সিকোয়েন্স।

ইনপুট এবং আউটপুট

ইনপুট: দুটি স্ট্রিং। "ABCDEF" এবং "XYDEF" আউটপুট: সর্বনিম্ন সাধারণ সুপার-সিকোয়েন্সের দৈর্ঘ্য। এখানে সুপার-সিকোয়েন্স হল "ABCDEFXY"। তাই দৈর্ঘ্য ৮।

অ্যালগরিদম

superSeq(str1, str2)

ইনপুট: দুটি স্ট্রিং str1 এবং str2।

আউটপুট: সুপার সিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করুন।

শুরু 
  m := str1-এর দৈর্ঘ্য 
  n := str2-এর দৈর্ঘ্য 
  seqTab নামক টেবিল সংজ্ঞায়িত করুন আকার (m+1 x n+1) 
  i := 0 থেকে m পর্যন্ত, করুন 
    j := 0 থেকে n পর্যন্ত, করুন 
      যদি i = 0, তবে 
        seqTab[i, j] := j 
      অন্যথায় যদি j = 0, তবে 
        seqTab[i, j] := i 
      অন্যথায় যদি str1[i-1] = str2[j-1], তবে 
        seqTab[i, j] := 1 + seqTab[i-1, j-1] 
      অন্যথায় 
        seqTab[i, j] := 1 + seqTab[i-1, j] এবং seqTab[i, j-1]-এর ন্যূনতম 
    শেষ 
  শেষ 
  seqTab[m, n] ফেরত দিন 
শেষ

উদাহরণ

#include<iostream> using namespace std; int min(int a, int b) {   return (a<b)?a:b; } int superSeq(string str1, string str2) {   int m = str1.size();   int n = str2.size();   int supSeqTable[m+1][n+1];   for (int i = 0; i <= m; i++) {     for (int j = 0; j <= n; j++) {       if (!i)         supSeqTable[i][j] = j;       //সর্বনিম্ন সুপারসিকোয়েন্সের দৈর্ঘ্য j     else if (!j)         supSeqTable[i][j] = i;       //সর্বনিম্ন সুপারসিকোয়েন্সের দৈর্ঘ্য i     else if (str1[i-1] == str2[j-1])         supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];     else         supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);     }   }   return supSeqTable[m][n]; } int main() {   string first = "ABCDEF";   string second = "XYDEF";   cout << "Length of the shortest supersequence is " << superSeq(first, second); }

আউটপুট

সর্বনিম্ন সুপারসিকোয়েন্সের দৈর্ঘ্য ৮