programa en C ++ para imprimir todas las subsecuencias de una cuerda

Aquí, estamos implementando un programa C ++ que imprime todas las subsecuencias de una cadena .

Descripción: Solución para imprimir todas las subsecuencias de una cadena usando el programa C ++.

Planteamiento del problema:

Escribir un programa que acepte la entrada de usuario e imprimir todas las subsecuencias de esa cadena.

Ejemplo:

    Input: abcd
Output: : a ab abcabcdabd ac acd ad b bcbcd bd c cd d

Explicación:

Lo que es Subsequences?

Una subsecuencia es una secuencia generada cadena froma después de eliminar algunos caracteres de cadena sin cambiar el orden de caracteres de cadena restantes.

class ejemplo, si tenemos una cadena: “abc” , entonces sus subsecuencias son: – “a” , “b” , “c” , “ab” , ” ac” , “BC” , “abc”

  • en primer lugar seleccionamos primer carácter es decir, ‘a’, imprimirlo y solucionarlo. —-> a
  • Tome próxima For es decir, ‘b’, imprimirlo y fijarlo —-> ab
  • Siga tomando siguientes caracteres hasta extremos de cadena —-> abc
  • Eliminar hasta primera char, empezar a tomar char del segundo
  • posición desde la primera hasta la char extremos de cadena —-> ac
  • del mismo modo ir char de descanso caracteres —-> b, bc, c
  • también tenemos un resultado :
    Si tenemos cadena de longitud N. Entonces el número de sus subsecuencias no vacíos es (2n-1).

Subsequence vs Subcadena

Hay diferencia entre subsecuencia y subcadena. Muchas veces la gente piensa que estos términos son iguales, pero son totalmente diferentes.

Subcadena es la parte contigua de la cadena. Si hay una cadena de longitud n, entonces su número de subcadenas son n * (n + 1) / 2 .

for ejemplo, si tenemos una cadena: “abc” , entonces sus subseries son: – “a” , “b” , “c” , “ab” , ” bc” , “abc”

Algoritmo:

  1. Conjunto start = -1 , final = len , donde len = longitud de la cuerda .
  2. Conjunto curStr = “” , imprimirlo
  3. carácter Fix y agregarlo en curStr e imprimir curStr .
  4. For i = 1 comenzar a final
    carácter Fix en curStr e imprime la cadena
  5. recursiva generar todos los subconjuntos a partir de carácter fijo.
  6. Después de cada llamada recursiva, eliminar el último carácter para generar la siguiente secuencia.
  7. Borrar el curStr
  8. Conjunto start = start + 1
  9. si < n inicio, vaya al paso 3.
  10. parada.

Complejidad de tiempo: O (2n)

Código

#include <iostream>
#include <string>
using namespace std;
void printSubsequences(string str, int start, int end, string curStr = ""){
//base case
if (start == end) {
return;
}
//print current string permutation
cout<<curStr<< " ";
for (int i = start + 1; i< end; i++) {
curStr += str[i];
printSubsequences(str, i, end, curStr);
curStr = curStr.erase(curStr.size() - 1);
}
}
int main(){
string s;
cout<< "Enter string : ";
cin>> s;
int len = s.size();
cout<< "Subsequences : ";
printSubsequences(s, -1, len);
return 0;
}

salida

Enter string : abcd
Subsequences : a ab abcabcdabd ac acd ad b bcbcd bd c cd d


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *