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:
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?
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 usarstring
.