Shortest Superstring Problem


StringViews 2407

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

 

Translate »