Home » Interview Questions » String Interview Questions » Shortest Superstring Problem

Shortest Superstring Problem


()

Given array of strings, write a function that will print the smallest string that contains each string in the array as substring

Example

INPUT

arr[] = {“catlog”, “dog”, “loggk”, “xcatdo” }

OUTPUT
“catloggkxcatdog”

In the output string, all the strings in the given array are substrings

Algorithm

1. Create a auxiliary array temp[], and copy all the strings of arr[] into temp[]

2. Till Temp[] contains more than two strings
a. Find the most overlapping string pair in temp[]. Let this pair be ‘s1’ and ‘s2’.
b. Replace ‘s1’ and ‘s2’ with the string obtained after combining them

3. At the end, temp[] contains the resultant string

Implementation of algorithm for above example :

arr[] =  {“catlog”, “dog”, “loggk”, “xcatdo” }
temp[] =  {“catlog”, “dog”, “loggk”, “xcatdo” }

First most overlappig pair is “catlog” and “loggk”
Merge Them, “catloggk”

Now, temp[] = {“catloggk”, “dog”, “xcatdo”}
Most overlapping pair is “dog” and “xcatdo”
Merger Them, “xcatdog”

Now, temp[] = {“catloggk”, “dogxcatdo” }
No overlapping so just merge them
res = “catloggkxcatdog”

#include <bits/stdc++.h>
using namespace std;
 
// Utility function to calculate minimum of two numbers
int min(int a, int b)
{
    return (a < b) ? a : b;
}
 
// Function to calculate maximum overlap in two given strings
int findOverlappingPair(string s1, string s2, string &s)
{
    // max will store maximum length of the matching prefix and suffix
    int max = INT_MIN;
    int len1 = s1.length();
    int len2 = s2.length();
 
    // check suffix of s1 matches with prefix of s2
    for (int i = 1; i <= min(len1, len2); i++)
    {
        // compare last i characters in s1 with first i
        // characters in s2
        if (s1.compare(len1-i, i, s2, 0, i) == 0)
        {
            if (max < i)
            {
                //update max and s
                max = i;
                s = s1 + s2.substr(i);
            }
        }
    }
 
    // check prefix of s1 matches with suffix of s2
    for (int i = 1; i <= min(len1, len2); i++)
    {
        // compare first i characters in s1 with last i
        // characters in s2
        if (s1.compare(0, i, s2, len2-i, i) == 0)
        {
            if (max < i)
            {
                //update max and s
                max = i;
                s = s2 + s1.substr(i);
            }
        }
    }
 
    return max;
}
 
// Function to find shortest superstring
string findShortestSuperstring(string arr[], int n)
{
    // run n-1 times to consider every pair
    while(n != 1)
    {
        int max = INT_MIN;  // to store  maximum overlap
        int l, r;   // to store array index of overlaping strings
        string res;  // to store resultant string after overlap
 
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                string s;
 
                // max_len will store maximum length of the matching
                int max_len = findOverlappingPair(arr[i], arr[j], s);
                // prefix and suffix s is passed by reference.
                if (max < max_len)
                {
                    // will store the resultant string after maximum
                    // overlap of arr[i] and arr[j],
                    max = max_len;
                    res.assign(s);
                    l = i, r = j;
                }
            }
        }
 
        n--;  //ignore last element in next cycle
 
        // if no overlap, append arr[n] to arr[0]
        if (max == INT_MIN)
            arr[0] += arr[n];
        else
        {
            arr[l] = res;   // copy resultant string to index l
            arr[r] = arr[n];  // copy string at last index to index r
        }
    }
    return arr[0];
}
 
// Driver program
int main()
{
    string arr[] =  {"catlog", "dog", "loggk", "xcatdo" };
    int n = sizeof(arr)/sizeof(arr[0]);
 
    cout << "The Shortest Superstring is "
         << findShortestSuperstring(arr, n)<<endl;
 
    return 0;
}

Try It

READ  Word Pattern

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions