## 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;
}
```