Estructura de datos de cuerdas (concatenación rápida de strings)

Una de las operaciones más comunes en strings es agregar o concatenar. Agregar al final de una string cuando la string se almacena de la manera tradicional (es decir, una array de caracteres) tomaría un tiempo mínimo de O (n) (donde n es la longitud de la string original). 
Podemos reducir el tiempo que lleva anexar utilizando la estructura de datos de cuerdas. 
 

Una cuerda es una estructura de árbol binario donde cada Node, excepto los Nodes hoja, contiene el número de caracteres presentes a la izquierda de ese Node . Los Nodes hoja contienen la string real dividida en substrings (el usuario puede decidir el tamaño de estas substrings).
Considere la imagen de abajo.
 

La imagen muestra cómo se almacena la string en la memoria. Cada Node hoja contiene substrings de la string original y todos los demás Nodes contienen la cantidad de caracteres presentes a la izquierda de ese Node. La idea detrás de almacenar el número de caracteres a la izquierda es minimizar el costo de encontrar el carácter presente en la i-ésima posición.
Ventajas 
1. Las cuerdas reducen drásticamente el costo de agregar dos cuerdas. 
2. A diferencia de los arreglos, las cuerdas no requieren grandes asignaciones de memoria contiguas. 
3. Las cuerdas no requieren O(n) memoria adicional para realizar operaciones como inserción/borrado/búsqueda. 
4. En caso de que un usuario quiera deshacer la última concatenación realizada, puede hacerlo en tiempo O(1) simplemente eliminando el Node raíz del árbol.
Desventajas 
1. La complejidad del código fuente aumenta. 
2. Mayores posibilidades de errores. 
3. Se requiere memoria adicional para almacenar Nodes principales. 
4. Aumenta el tiempo para acceder al i-ésimo carácter.
Ahora veamos una situación que explica por qué las cuerdas son un buen sustituto de las arrays monolíticas de cuerdas.  
Dadas dos strings a[] y b[]. Concatenarlos en una tercera string c[].
Ejemplos: 
 

Input  : a[] = "This is ", b[] = "an apple"
Output : "This is an apple"

Input  : a[] = "This is ", b[] = "geeksforgeeks"
Output : "This is geeksforgeeks"

Creamos una string c[] para almacenar strings concatenadas. Primero recorremos a[] y copiamos todos los caracteres de a[] a c[]. Luego copiamos todos los caracteres de b[] a c[]. 
Implementación: 

// Simple C++ program to concatenate two strings
#include <iostream>
using namespace std;
 
// Function that concatenates strings a[0..n1-1]
// and b[0..n2-1] and stores the result in c[]
void concatenate(char a[], char b[], char c[],
                              int n1, int n2)
{
    // Copy characters of A[] to C[]
    int i;
    for (i=0; i<n1; i++)
        c[i] = a[i];
 
    // Copy characters of B[]
    for (int j=0; j<n2; j++)
        c[i++] = b[j];
 
    c[i] = '\0';
}
 
 
// Driver code
int main()
{
    char a[] =  "Hi This is geeksforgeeks. ";
    int n1 = sizeof(a)/sizeof(a[0]);
 
    char b[] =  "You are welcome here.";
    int n2 = sizeof(b)/sizeof(b[0]);
 
    // Concatenate a[] and b[] and store result
    // in c[]
    char c[n1 + n2 - 1];
    concatenate(a, b, c, n1, n2);
    for (int i=0; i<n1+n2-1; i++)
        cout << c[i];
 
    return 0;
}

//Java program to concatenate two strings
 
class GFG {
 
    // Function that concatenates strings a[0..n1-1]
    // and b[0..n2-1] and stores the result in c[]
    static void concatenate(char a[], char b[], char c[],
            int n1, int n2) {
        // Copy characters of A[] to C[]
        int i;
        for (i = 0; i < n1; i++) {
            c[i] = a[i];
        }
 
        // Copy characters of B[]
        for (int j = 0; j < n2; j++) {
            c[i++] = b[j];
        }
 
    }
 
    // Driver code
    public static void main(String[] args) {
        char a[] = "Hi This is geeksforgeeks. ".toCharArray();
        int n1 = a.length;
 
        char b[] = "You are welcome here.".toCharArray();
        int n2 = b.length;
 
        // Concatenate a[] and b[] and store result
        // in c[]
        char c[] = new char[n1 + n2];
        concatenate(a, b, c, n1, n2);
        for (int i = 0; i < n1 + n2 - 1; i++) {
            System.out.print(c[i]);
        }
 
    }
}
// This code is contributed by PrinciRaj1992

# Python3 program to concatenate two strings
 
# Function that concatenates strings a[0..n1-1]
# and b[0..n2-1] and stores the result in c[]
def concatenate(a, b, c, n1, n2):
 
    # Copy characters of A[] to C[]
    i = -1
    for i in range(n1):
        c[i] = a[i]
 
    # Copy characters of B[]
    for j in range(n2):
        c[i] = b[j]
        i += 1
 
# Driver Code
if __name__ == "__main__":
    a = "Hi This is geeksforgeeks. "
    n1 = len(a)
 
    b = "You are welcome here."
    n2 = len(b)
 
    a = list(a)
    b = list(b)
 
    # Concatenate a[] and b[] and
    # store result in c[]
    c = [0] * (n1 + n2 - 1)
 
    concatenate(a, b, c, n1, n2)
 
    for i in c:
        print(i, end = "")
 
# This code is contributed by
# sanjeev2552

// C# program to concatenate two strings
using System;
 
public class GFG {
  
    // Function that concatenates strings a[0..n1-1]
    // and b[0..n2-1] and stores the result in c[]
    static void concatenate(char []a, char []b, char []c,
            int n1, int n2) {
        // Copy characters of A[] to C[]
        int i;
        for (i = 0; i < n1; i++) {
            c[i] = a[i];
        }
  
        // Copy characters of B[]
        for (int j = 0; j < n2; j++) {
            c[i++] = b[j];
        }
  
    }
  
    // Driver code
    public static void Main() {
        char []a = "Hi This is geeksforgeeks. ".ToCharArray();
        int n1 = a.Length;
  
        char []b = "You are welcome here.".ToCharArray();
        int n2 = b.Length;
  
        // Concatenate a[] and b[] and store result
        // in c[]
        char []c = new char[n1 + n2];
        concatenate(a, b, c, n1, n2);
        for (int i = 0; i < n1 + n2 - 1; i++) {
            Console.Write(c[i]);
        }
  
    }
}
/*This code is contributed by PrinciRaj1992*/

Producción: 
 

Hi This is geeksforgeeks. You are welcome here

Complejidad del tiempo: O(n)
Ahora intentemos resolver el mismo problema usando cuerdas.
 

Esta estructura de cuerda se puede utilizar para concatenar dos strings en tiempo constante. 
1. Cree un nuevo Node raíz (que almacene la raíz de la nueva string concatenada) 
2. Marque el hijo izquierdo de este Node, la raíz de la string que aparece primero. 
3. Marque el hijo derecho de este Node, la raíz de la string que aparece en segundo lugar.
Y eso es. Dado que este método solo requiere crear un nuevo Node, su complejidad es O(1) .
Considere la imagen a continuación (Fuente de la imagen: https://en.wikipedia.org/wiki/Rope_(data_structure))
 

 Implementación:

// C++ program to concatenate two strings using
// rope data structure.
#include <bits/stdc++.h>
using namespace std;
 
// Maximum no. of characters to be put in leaf nodes
const int LEAF_LEN = 2;
 
// Rope structure
class Rope
{
public:
    Rope *left, *right, *parent;
    char *str;
    int lCount;
};
 
// Function that creates a Rope structure.
// node --> Reference to pointer of current root node
//   l  --> Left index of current substring (initially 0)
//   r  --> Right index of current substring (initially n-1)
//   par --> Parent of current node (Initially NULL)
void createRopeStructure(Rope *&node, Rope *par,
                         char a[], int l, int r)
{
    Rope *tmp = new Rope();
    tmp->left = tmp->right = NULL;
  
    // We put half nodes in left subtree
    tmp->parent = par;
  
    // If string length is more
    if ((r-l) > LEAF_LEN)
    {
        tmp->str = NULL;
        tmp->lCount = (r-l)/2;
        node = tmp;
        int m = (l + r)/2;
        createRopeStructure(node->left, node, a, l, m);
        createRopeStructure(node->right, node, a, m+1, r);
    }
    else
    {
        node = tmp;
        tmp->lCount = (r-l);
        int j = 0;
        tmp->str = new char[LEAF_LEN];
        for (int i=l; i<=r; i++)
            tmp->str[j++] = a[i];
    }
}
 
// Function that prints the string (leaf nodes)
void printstring(Rope *r)
{
    if (r==NULL)
        return;
    if (r->left==NULL && r->right==NULL)
        cout << r->str;
    printstring(r->left);
    printstring(r->right);
}
 
// Function that efficiently concatenates two strings
// with roots root1 and root2 respectively. n1 is size of
// string represented by root1.
// root3 is going to store root of concatenated Rope.
void concatenate(Rope *&root3, Rope *root1, Rope *root2, int n1)
{
    // Create a new Rope node, and make root1
    // and root2 as children of tmp.
    Rope *tmp = new Rope();
    tmp->parent = NULL;
    tmp->left = root1;
    tmp->right = root2;
    root1->parent = root2->parent = tmp;
    tmp->lCount = n1;
 
    // Make string of tmp empty and update
    // reference r
    tmp->str = NULL;
    root3 = tmp;
}
 
// Driver code
int main()
{
    // Create a Rope tree for first string
    Rope *root1 = NULL;
    char a[] =  "Hi This is geeksforgeeks. ";
    int n1 = sizeof(a)/sizeof(a[0]);
    createRopeStructure(root1, NULL, a, 0, n1-1);
 
    // Create a Rope tree for second string
    Rope *root2 = NULL;
    char b[] =  "You are welcome here.";
    int n2 = sizeof(b)/sizeof(b[0]);
    createRopeStructure(root2, NULL, b, 0, n2-1);
 
    // Concatenate the two strings in root3.
    Rope *root3 = NULL;
    concatenate(root3, root1, root2, n1);
 
    // Print the new concatenated string
    printstring(root3);
    cout << endl;
    return 0;
}

Producción: 
 

Hi This is geeksforgeeks. You are welcome here.

Complejidad de tiempo : O(1) 

Espacio auxiliar: O(1)
Este artículo es una contribución de Akhil Goel . 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.