Question

Find the shortest common superstring for eight 3-mers:

{AGT, AAA, ACT, AAC, CTT, GTA, TTT, TAA}

Answer 1

#include <bits/stdc++.h>
using namespace std;

int maxOverLapOfTwoStrings(string s1, string s2, string &str)
{
   // maxValue stores the max of prefix and suffix those are matching
   int maxValue= INT_MIN;
   int l1 = s1.length();
   int l2 = s2.length();

   //checking whether prefix of s2 is suffix of s1 or not
   for (int i = 1; i <= min(l1, l2); i++)
   {
       if (s1.compare(l1-i, i, s2, 0, i) == 0)
       {
           if (maxValue< i)
           {
               maxValue= i;
               str = s1 + s2.substr(i);
           }
       }
   }

   // validating whether prefix of s1 matches suffix of s2
   for (int i = 1; i <= min(l1, l2); i++)
   {
       if (s1.compare(0, i, s2, l2-i, i) == 0)
       {
           if (maxValue< i)
           {
               maxValue= i;
               str = s2 + s1.substr(i);
           }
       }
   }

   return maxValue;
}

string fun(string A[], int n )
{
   //consider each pair
   while(n != 1)
   {
       int maxValue= INT_MIN;
       int l, r;
       string ansStr; //resultant string after overlap

       for (int i = 0; i < n; i++)
       {
           for (int j = i + 1; j < n; j++)
           {
               string str;

               int ans = maxOverLapOfTwoStrings(A[i], A[j], str);

               //look for max overlap
               if (maxValue< ans)
               {
                   maxValue= ans;
                   ansStr.assign(str);
                   l = i, r = j;
               }
           }
       }

       n--;

       if (maxValue== INT_MIN)
           A[0] += A[n];
       else
       {
           A[l] = ansStr;
           A[r] = A[n];
       }
   }
   return A[0];
}

int main()
{
   string A[] ={"AGT", "AAA", "ACT", "AAC", "CTT", "GTA", "TTT", "TAA"};
   int n = sizeof(A)/sizeof(A[0]);

   cout << "For given 8 strings the shortest superstring is "<< fun(A, n);
   cout<<endl;
   return 0;
}

output -

For given 8 strings the shortest superstring is AGTAAACTTT