# Shortest Superstring Problem

StringViews 527

## 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
if (max == INT_MIN)
arr += 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;
}

// Driver program
int main()
{
string arr[] =  {"catlog", "dog", "loggk", "xcatdo" };
int n = sizeof(arr)/sizeof(arr);

cout << "The Shortest Superstring is "
<< findShortestSuperstring(arr, n)<<endl;

return 0;
}```

Translate »