Concatenación lexicográfica de todas las substrings de una string

Dada una string, encuentre la concatenación de todas las substrings en orden lexicográfico.
Ejemplos: 
 

Entrada: s = “abc” 
Salida: aababcbbcc 
Las substrings de s en orden lexicográfico son “a”, “b”, “c”, “ab”, “abc”, “bc”. La concatenación de substrings es “a”+”ab”+”abc”+”b”+”bc”+”c” = “aababcbbcc”.
Entrada: s = “cba” 
Salida: abbaccbcba 
 

 

1. Encuentre todas las substrings de string y guárdelas en una array de strings. El tamaño de la array sería n*(n+1)/2 donde n es la longitud de la string de entrada. 
2. Ordene la array de strings para que estén todas en orden lexicográfico. 
3. Concatene las strings de la array de strings en otra string vacía.
 

C++

// CPP Program to create concatenation of all // substrings in lexicographic order. #include <bits/stdc++.h> using namespace std;    string lexicographicSubConcat(string s) {     int n = s.length();        // Creating an array to store substrings     int sub_count = n*(n+1)/2;     string arr[sub_count];             // finding all substrings of string     int index = 0;     for (int i = 0; i < n; i++)          for (int len = 1; len <= n - i; len++)              arr[index++] = s.substr(i, len);            // Sort all substrings in lexicographic     // order     sort(arr, arr + sub_count);         // Concatenating all substrings     string res = "";     for (int i = 0; i < sub_count; i++)          res += arr[i];                     return res;     }    int main() {     string s = "abc";      cout << lexicographicSubConcat(s);     return 0; }

Java

// Java Program to create concatenation of all // substrings in lexicographic order. import java.util.*;    class GFG  {           static String lexicographicSubConcat(String s) {     int n = s.length();        // Creating an array to store substrings     int sub_count = n*(n+1)/2;     String []arr = new String[sub_count];             // finding all substrings of string     int index = 0;     for (int i = 0; i < n; i++)          for (int len = 1; len <= n - i; len++)          {                 arr[index++] = s.substring(i, i+len);         }     // Sort all substrings in lexicographic     // order     Arrays.sort(arr);         // Concatenating all substrings     String res = "";     for (int i = 0; i < sub_count; i++)          res += arr[i];                     return res;  }    // Driver code public static void main(String[] args)  {     String s = "abc";      System.out.println(lexicographicSubConcat(s)); } }    // This code has been contributed by 29AjayKumar

Python3

# Python Program to create concatenation of all # substrings in lexicographic order.    def lexicographicSubConcat(s):     n = len(s);        # Creating an array to store substrings     sub_count = (n * (n + 1))//2;     arr = [0]*sub_count;             # finding all substrings of string     index = 0;     for i in range(n):         for j in range(1,n - i + 1):             arr[index] = s[i:i + j];             index += 1;            # Sort all substrings in lexicographic     # order     arr.sort();         # Concatenating all substrings     res = "";     for i in range(sub_count):         res += arr[i];                     return res;     s = "abc";  print(lexicographicSubConcat(s));    # This code is contributed by Princi Singh

C#

// C# Program to create concatenation of all // substrings in lexicographic order. using System;             class GFG  {        static String lexicographicSubConcat(String s) {     int n = s.Length;        // Creating an array to store substrings     int sub_count = n*(n+1)/2;     String []arr = new String[sub_count];             // finding all substrings of string     int index = 0;     for (int i = 0; i < n; i++)          for (int len = 1; len <= n - i; len++)          {             arr[index++] = s.Substring(i, len);         }                // Sort all substrings in lexicographic     // order     Array.Sort(arr);         // Concatenating all substrings     String res = "";     for (int i = 0; i < sub_count; i++)          res += arr[i];                     return res;  }    // Driver code public static void Main(String[] args)  {     String s = "abc";      Console.WriteLine(lexicographicSubConcat(s)); } }    /* This code contributed by PrinciRaj1992 */

JavaScript

<script>    // Javascript Program to create concatenation of all // substrings in lexicographic order.    function lexicographicSubConcat(s) {     var n = s.length;        // Creating an array to store substrings     var sub_count = n*parseInt((n+1)/2);     var arr = Array(sub_count);             // finding all substrings of string     var index = 0;     for (var i = 0; i < n; i++)          for (var len = 1; len <= n - i; len++)              arr[index++] = s.substring(i,i+ len);            // Sort all substrings in lexicographic     // order     arr.sort();        // Concatenating all substrings     var res = "";     for (var i = 0; i < sub_count; i++)          res += arr[i];                     return res;     }    var s = "abc";  document.write( lexicographicSubConcat(s));    </script>

Producción: 
 

aababcbbcc

Complejidad temporal: O(n ³ )

Espacio Auxiliar: O(n)
 

 Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.