Substring Sort | C ++ Program to sort substrings ; sort the input array ; repeated length should be the same string ; two different strings with the same length input array cannot be sorted ; validate that each string is a substring of the following one ; get first element ; The array is valid and sorted print the strings in order ; Test 1 ; Test 2
#include <bits/stdc++.h> NEW_LINE using namespace std ; void substringSort ( string arr [ ] , int n , int maxLen ) { int count [ maxLen ] ; string sortedArr [ maxLen ] ; for ( int i = 0 ; i < maxLen ; i ++ ) { count [ i ] = 0 ; sortedArr [ i ] = " " ; } for ( int i = 0 ; i < n ; i ++ ) { string s = arr [ i ] ; int len = s . length ( ) ; if ( count [ len - 1 ] == 0 ) { sortedArr [ len - 1 ] = s ; count [ len - 1 ] = 1 ; } else if ( sortedArr [ len - 1 ] == s ) { count [ len - 1 ] ++ ; } else { cout << " Cannot ▁ be ▁ sorted " ; return ; } } int index = 0 ; while ( count [ index ] == 0 ) index ++ ; int prev = index ; string prevString = sortedArr [ prev ] ; index ++ ; for ( ; index < maxLen ; index ++ ) { if ( count [ index ] != 0 ) { string current = sortedArr [ index ] ; if ( current . find ( prevString ) != string :: npos ) { prev = index ; prevString = current ; } else { cout << " Cannot ▁ be ▁ sorted " ; return ; } } } for ( int i = 0 ; i < maxLen ; i ++ ) { string s = sortedArr [ i ] ; for ( int j = 0 ; j < count [ i ] ; j ++ ) { cout << s << endl ; } } } int main ( ) { int maxLen = 100 ; string arr1 [ ] = { " d " , " zddsaaz " , " ds " , " ddsaa " , " dds " , " dds " } ; substringSort ( arr1 , sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) , maxLen ) ; string arr2 [ ] = { " for " , " rof " } ; substringSort ( arr2 , sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) , maxLen ) ; return 0 ; }