Para resolver este problema, primero podemos pensar en: “¿cuántas subcadenas de longitud 1 se pueden formar a partir de una cadena de caracteres de longitud n?”
Es una respuesta simple. Si tomamos el paso de 1 carácter, podemos desde n subcadenas de la cadena original (vamos a llamarlo s) .
Por ejemplo, si s = “abcde”, s con longitud n = 5, podemos formar estas subcadenas de longitud 1 : “a”, “b”, “c”, “d”, “e” (5). Entonces, formamos n subcadenas.
- ¿Qué debo saber sobre C ++ antes de poder escribir 'competente en C ++' en mi currículum?
- ¿Puedes usar JavaScript en la programación de entrevistas?
- Cómo prepararse para una entrevista que forma parte del PGEE IIIT-H
- ¿Cuáles son los requisitos previos para programar entrevistas en empresas tecnológicas y recomendar libros?
- ¿Debo molestarme en solicitar un trabajo de desarrollador si estoy seguro de que no puedo descifrar la entrevista técnica?
Pero en la pregunta original, queremos saber cuántas subcadenas de cualquier longitud. Esta respuesta no es suficiente.
Veamos cuántas subcadenas de longitud 2 se pueden formar. Vamos a dar un paso de 1 carácter, en el ejemplo:
si s = “abcde”, s con longitud n = 5, podemos formar estas subcadenas de longitud 2 : “ab”, “bc”, “cd”, “de” (4). Porque, cuando llegamos a la “e”, no podemos formar una subcadena de dos longitudes. No hay suficientes personajes a continuación. Entonces, formamos n-1 subcadenas.
Algo similar sucederá con las subcadenas de longitud 3. Podemos formar n-2 subcadenas, y así sucesivamente.
Entonces, si pensamos en cualquier cadena s, podemos concluir que podemos formar:
- n subcadenas de longitud 1
- n-1 subcadenas de longitud 2
- n-2 subcadenas de longitud 3
- … pronto
- 1 subcadenas de longitud n
Podemos resumir todos esos resultados para saber “¿cuántas subcadenas de cualquier longitud se pueden formar a partir de una cadena de caracteres de longitud n?”
- n + n-1 + n-2 + n-3 + n-4 +…. + 1
La respuesta es una expresión de suma matemática. Podemos escribirlo de otra manera:
Fuente: Summation – Wikipedia Summation – Wikipedia
Entonces, la respuesta final a la pregunta “¿cuántas subcadenas se pueden formar a partir de una cadena de caracteres de longitud n?” Es: (n * (n + 1)) / 2