Shortest Superstring Problem | C ++ program to find shortest superstring using Greedy Approximate Algorithm ; Utility function to calculate minimum of two numbers ; Function to calculate maximum overlap in two given strings ; Max will store maximum overlap i . e maximum length of the matching prefix and suffix ; Check suffix of str1 matches with prefix of str2 ; Compare last i characters in str1 with first i characters in str2 ; Update max and str ; Check prefix of str1 matches with suffix of str2 ; compare first i characters in str1 with last i characters in str2 ; Update max and str ; Function to calculate smallest string that contains each string in the given set as substring . ; Run len - 1 times to consider every pair ; To store maximum overlap ; To store array index of strings ; to store resultant string after maximum overlap ; res will store maximum length of the matching prefix and suffix str is passed by reference and will store the resultant string after maximum overlap of arr [ i ] and arr [ j ] , if any . ; check for maximum overlap ; Ignore last element in next cycle ; If no overlap , append arr [ len ] to arr [ 0 ] ; Copy resultant string to index l ; Copy string at last index to index r ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int min ( int a , int b ) { return ( a < b ) ? a : b ; } int findOverlappingPair ( string str1 , string str2 , string & str ) { int max = INT_MIN ; int len1 = str1 . length ( ) ; int len2 = str2 . length ( ) ; for ( int i = 1 ; i <= min ( len1 , len2 ) ; i ++ ) { if ( str1 . compare ( len1 - i , i , str2 , 0 , i ) == 0 ) { if ( max < i ) { max = i ; str = str1 + str2 . substr ( i ) ; } } } for ( int i = 1 ; i <= min ( len1 , len2 ) ; i ++ ) { if ( str1 . compare ( 0 , i , str2 , len2 - i , i ) == 0 ) { if ( max < i ) { max = i ; str = str2 + str1 . substr ( i ) ; } } } return max ; } string findShortestSuperstring ( string arr [ ] , int len ) { while ( len != 1 ) { int max = INT_MIN ; int l , r ; string resStr ; for ( int i = 0 ; i < len ; i ++ ) { for ( int j = i + 1 ; j < len ; j ++ ) { string str ; int res = findOverlappingPair ( arr [ i ] , arr [ j ] , str ) ; if ( max < res ) { max = res ; resStr . assign ( str ) ; l = i , r = j ; } } } len -- ; if ( max == INT_MIN ) arr [ 0 ] += arr [ len ] ; else { arr [ l ] = resStr ; arr [ r ] = arr [ len ] ; } } return arr [ 0 ] ; } int main ( ) { string arr [ ] = { " catgc " , " ctaagt " , " gcta " , " ttca " , " atgcatc " } ; int len = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " The ▁ Shortest ▁ Superstring ▁ is ▁ " << findShortestSuperstring ( arr , len ) ; return 0 ; }