Substring en C++ – Part 1

En C++, std::substr() es una función predefinida utilizada para el manejo de strings. string.h es el archivo de encabezado requerido para las funciones de string. 
Esta función toma dos valores pos y len como argumento y devuelve un objeto de string recién construido con su valor inicializado en una copia de una substring de este objeto. La copia de la string comienza desde pos y se realiza hasta que pos+len significa [pos, pos+len) .

Puntos importantes:  

1. El índice del primer carácter es 0 (no 1).
2. Si pos es igual a la longitud de la string, la función devuelve una string vacía.
3. Si pos es mayor que la longitud de la string, lanza out_of_range. Si esto sucede, no hay cambios en la string.
4. Si la substring solicitada len es mayor que el tamaño de una string, la substring devuelta es [pos, size()) .
5. Si no se pasa len como parámetro, la substring devuelta es [pos, tamaño()).

Sintaxis: 

string substr (size_t pos, size_t len) const;

Parámetros:

1. pos: Posición del primer carácter a copiar.
2. len: Longitud de la substring.
3. size_t: Es un tipo integral sin signo.

Valor de retorno: 

Devuelve un objeto de string.

Ejemplo:

// CPP program to illustrate substr()
#include <string.h>
#include <iostream>
using namespace std;
  
int main()
{
    // Take any string
    string s1 = "Geeks";
  
    // Copy two characters of s1 (starting 
    // from position 3)
    string r = s1.substr(3, 2);
  
    // prints the result
    cout << "String is: " << r;
  
    return 0;
}

String is: ks

Complejidad temporal: O(n)

Espacio Auxiliar: O(n)

Aplicaciones:

1. ¿Cómo obtener una substring después de un carácter? 

En esto, se dan una string y un carácter y debe imprimir la substring seguida del carácter dado. 
Extraiga todo lo que esté después de “:” en la string “ perro:gato ” .

Ejemplo:

// CPP program to illustrate substr()
#include <string.h>
#include <iostream>
using namespace std;
  
int main()
{
    // Take any string
    string s = "dog:cat";
  
    // Find position of ':' using find()
    int pos = s.find(":");
  
    // Copy substring after pos
    string sub = s.substr(pos + 1);
  
    // prints the result
    cout << "String is: " << sub;
  
    return 0;
}

String is: cat

Complejidad temporal: O(n)

Espacio Auxiliar: O(n)                    

2. ¿Cómo obtener una substring antes de un carácter? 

En esto, se dan una string y un carácter y debe imprimir la substring seguida del carácter dado. 
Extraiga todo antes de «:» en la string » perro:gato «. 

Ejemplo:

// CPP program to illustrate substr()
#include <string.h>
#include <iostream>
using namespace std;
  
int main()
{
    // Take any string
    string s = "dog:cat";
  
    // Find position of ':' using find()
    int pos = s.find(":");
  
    // Copy substring before pos
    string sub = s.substr(0 , pos);
  
    // prints the result
    cout << "String is: " << sub;
  
    return 0;
}

String is: dog

Complejidad temporal: O(n)

Espacio Auxiliar: O(n)

3. Imprime todas las substrings de una string dada

Dada una string como entrada. Necesitamos escribir un programa que imprima todas las substrings no vacías de esa string dada.

Ejemplo:

// C++ program to demosntrate all possible
// substrings of a given string
#include <bits/stdc++.h>
using namespace std;
  
// Function to print all sub strings
void subString(string s, int n)
{
    // Pick starting point in outer loop
    // and lengths of different strings for
    // a given starting point
    for (int i = 0; i < n; i++)
        for (int len = 1; len <= n - i; len++)
            cout << s.substr(i, len) << endl;
}
  
// Driver program to test above function
int main()
{
    string s = "abcd";
    subString(s, s.length());
    return 0;
}

a
ab
abc
abcd
b
bc
bcd
c
cd
d

Complejidad temporal: O( n ³ )

Espacio Auxiliar: O(1)

4. Suma de todas las substrings de una string que representa un número

Dado un entero representado como una string, necesitamos obtener la suma de todas las substrings posibles de esta string.

Ejemplo:

// C++ program to print sum of all substring of
// a number represented as a string
#include <bits/stdc++.h>
using namespace std;
  
// Utility method to convert character digit to
// integer digit
int toDigit(char ch)
{
    return (ch - '0');
}
  
// Returns sum of all substring of num
int sumOfSubstrings(string num)
{
    int n = num.length();
  
    // allocate memory equal to length of string
    int sumofdigit[n];
  
    // initialize first value with first digit
    sumofdigit[0] = toDigit(num[0]);
    int res = sumofdigit[0];
  
    // loop over all digits of string
    for (int i = 1; i < n; i++) {
        int numi = toDigit(num[i]);
  
        // update each sumofdigit from previous value
        sumofdigit[i] = (i + 1) * numi + 10 * sumofdigit[i - 1];
  
        // add current value to the result
        res += sumofdigit[i];
    }
  
    return res;
}
  
// Driver code to test above methods
int main()
{
    string num = "1234";
    cout << sumOfSubstrings(num) << endl;
    return 0;
}

1670

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)