Shortest Superstring Problem | Java 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 ; pdate 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 involved in maximum overlap ; 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 Code
import java . io . * ; import java . util . * ; class GFG { static String str ; static int min ( int a , int b ) { return ( a < b ) ? a : b ; } static int findOverlappingPair ( String str1 , String str2 ) { int max = Integer . MIN_VALUE ; int len1 = str1 . length ( ) ; int len2 = str2 . length ( ) ; for ( int i = 1 ; i <= min ( len1 , len2 ) ; i ++ ) { if ( str1 . substring ( len1 - i ) . compareTo ( str2 . substring ( 0 , i ) ) == 0 ) { if ( max < i ) { max = i ; str = str1 + str2 . substring ( i ) ; } } } for ( int i = 1 ; i <= min ( len1 , len2 ) ; i ++ ) { if ( str1 . substring ( 0 , i ) . compareTo ( str2 . substring ( len2 - i ) ) == 0 ) { if ( max < i ) { max = i ; str = str2 + str1 . substring ( i ) ; } } } return max ; } static String findShortestSuperstring ( String arr [ ] , int len ) { while ( len != 1 ) { int max = Integer . MIN_VALUE ; int l = 0 , r = 0 ; String resStr = " " ; for ( int i = 0 ; i < len ; i ++ ) { for ( int j = i + 1 ; j < len ; j ++ ) { int res = findOverlappingPair ( arr [ i ] , arr [ j ] ) ; if ( max < res ) { max = res ; resStr = str ; l = i ; r = j ; } } } len -- ; if ( max == Integer . MIN_VALUE ) arr [ 0 ] += arr [ len ] ; else { arr [ l ] = resStr ; arr [ r ] = arr [ len ] ; } } return arr [ 0 ] ; } public static void main ( String [ ] args ) { String [ ] arr = { " catgc " , " ctaagt " , " gcta " , " ttca " , " atgcatc " } ; int len = arr . length ; System . out . println ( " The ▁ Shortest ▁ Superstring ▁ is ▁ " + findShortestSuperstring ( arr , len ) ) ; } }