3

Estoy haciendo un código que determina el numero de subcadenas posibles en una cadena de texto. Las subcadenas pueden ser de todas las longitudes posibles, pero deben estar ordenadas de forma alfabética. La entrada consiste en un entero n que representa el numero de cadenas, un numero que determina la longitud de la cadena y la cadena de letras. La salida es el numero de subcadenas posibles ordenadas para cada una. Ejemplo:

introducir la descripción de la imagen aquí

El código que ejecuté fue el siguiente:

#include <iostream>
using namespace std;

int main(){
    int T, j, k, N, i=0;
    cin>>T;
    while (i<T){
        cin >> N;
        int sub=N;
        char S[N];
        cin>>S;
        for (k=N;k>0;--k){
            for (j=0;j<k-1;++j){
                if(j==N && S[j]<=S[j+1]){
                    sub++;
                    S[j]=1;
                } else if (k==N){
                        S[j]=0;
                }else if(S[j]&&S[j+1]==1){
                    S[j]=S[j]&&S[j+1];
                    sub++;

                }else {
                    S[j]=0;
                }
            }
        }
        cout<<sub<<endl;
        i++;
    }

No obstante, el codigo debe ejecutarse en menos de 1 segundo, pero este se demora 1.48 segundos. ¿Cómo hago para hacerlo más eficiente?¿qué me recomiendan?

1
  • Si vas a guardar la cadena en un char[], el array ha de tener como longitud uno más que la cadena a guardar, porque hay un \0 al final. Si no lo haces, tienes undefined behavior (se escribe fuera del array). En todo caso, siendo C++ se recomienda usar string.
    – SJuan76
    Commented el 5 oct. 2018 a las 21:09

1 respuesta 1

3

Una posible solución:

#include <iostream>

int main( ) {
  int count;
  int length;
  char *string = nullptr;

  std::cin >> count;

  for( int n = 0; n < count; ++n ) {
    std::cin >> length;

    string = new char[length + 1];
    string[length] = 0;

    std::cin >> string;

    const char *start = string;
    int sublen = 0;

    while( *start ) {
      ++sublen;
      const char *curr = start + 1;
      while( ( *curr ) && ( *curr >= *( curr - 1 ) ) ) {
        ++sublen;
        ++curr;
      }
      ++start;
    }

    std::cout << "Combinaciones: " << sublen << '\n';
    delete[] string;
  }

  return 0;
}

Me parecía divertido, así que no me baso en tu código; está escrito desde 0.

No lo he cronometrado, pero creo que tarda menos de 1 seg. en ejecutarse. Y si añadieramos un poco de gestión extra de memoria (o usáramos std::string, que reutiliza el buffer de memoria si le es posible, como te indican en los comentarios) aun tardaría menos :-)

Compilado con g++ -std=c++11 -Wall -Wextra -pedantic.

2
  • Muchas gracias. Me sirvio de maravilla. Y tu solucion me parecio mas practica. Pero no entendi un aspecto particular, por que usaste el nullptr? Sin este el codigo igual me funciono y en otro compilador no me sirvio, por lo que lo suprimi
    – Jsanabria
    Commented el 5 oct. 2018 a las 22:26
  • @Jsanabria De echo, esa variable se puede dejar sin inicializar que no pasa nada. La costumbre; que los dedos escriben solos a veces :-)
    – Trauma
    Commented el 6 oct. 2018 a las 6:21

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.