সংক্ষিপ্ত কমন সুপার সিকোয়েন্স

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

যখন দুটি স্ট্রিং-এ কোনো সাধারণ অক্ষর থাকে না, তখন আমরা সুপার-সিকোয়েন্স পাওয়ার জন্য তাদের সহজভাবে সংযুক্ত করতে পারি। কিন্তু যখন তাদের কিছু সাধারণ অক্ষর থাকে, তখন প্রথমে আমাদের দীর্ঘতম স্ট্রিংটি খুঁজে বের করতে হবে, তারপরে অন্য স্ট্রিংয়ের অতিরিক্ত অক্ষর যোগ করতে হবে।

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

Input:
Two strings. “ABCDEF” and “XYDEF”
Output:
The length of the shortest common super-sequence.
Here the super-sequence is “ABCDEFXY”. So the length is 8.

অ্যালগরিদম

superSeq(str1, str2)

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

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

Begin
   m := length of str1
   n := length of str2
   define table named seqTab of size (m+1 x n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0, then
            seqTab[i, j] := j
         else if j = 0, then
            seqTab[i, j] := i
         else if str1[i-1] = str2[j-1], then
            seqTab[i, j] := 1 + seqTab[i-1, j-1]
         else
            seqTab[i, j] := 1 + minimum of seqTab[i-1, j] and seqTab[i, j-1]
      done
   done
   return seqTab[m, n]
End

উদাহরণ

#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;              //shortest supersequence length is j
         else if (!j)
            supSeqTable[i][j] = i;                //shortest supersequence length is 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);
}

আউটপুট

Length of the shortest supersequence is 8