Estructura de datos: Si la cadena S=‘software’, ¿cuántas subcadenas tiene? Proceso de resolución de problemas

En primer lugar, el software no tiene caracteres repetidos y tiene una longitud de 8

Hay 8 subcadenas de 1 carácter

Hay 8 subcadenas de; 2 caracteres. 1;

Hay 8-2 subcadenas de 3 caracteres;

Hay 8-6 subcadenas de 7 caracteres;

8 Hay 8 -7 subcadenas de caracteres.

Entonces el número total de subcadenas es 1+2+3...+8=36.

En muchos casos, las subcadenas se repiten, por ejemplo: abbbc, solo hay 11 subcadenas, 3+2+3+2+1=, no 1+2+3+4+5= 15. Otro ejemplo, abab, tiene 2+2+2+1 subcadenas. Por lo tanto, al programar, es necesario eliminar las subcadenas repetidas.

Información ampliada:

La subcadena de ab: a, b, ab*** 3, es decir (2+1), la subcadena de abc: a, b, c , ab, bc, abc*** (3+2+1), entonces si la longitud de la cadena es n, el número de subcadenas es [n*(n+1)/2], "software" El número de cadenas de neutrones es 8+7+....+1=36. Más una cadena vacía, eso es 37.

Para subcadenas con subcadenas idénticas consecutivas (por ejemplo: AAABBBCCC), el método de cálculo es n(n+1)/2+1 subcadenas repetidas.

Subcadena de la Enciclopedia Baidu