Una clase especial de cadenas X33813

En matemáticas, una subsecuencia en una cadena, es la secuencia de caracteres dentro de la cadena, que respetan el orden, mas no necesariamente deben aparecer de manera contigua. Es una forma de generalización de la subcadena, donde los caracteres deben estar consecutivos. Por ejemplo, la cadena ABCDEF tiene la subsecuencia ABD; observe que se respeta el orden de aparición, pero no todos los caracteres necesariamente están contiguos. POr otro lado, la secuencia DEA no es una subsecuencia de ABCDEF, ya que no respetan el orden. Un problema interesante en cadenas es el conteo de subsecuencias, escriba un programa que lea dos cadenas $s_1$ y $s_2$ e imprima cuantas veces aparece repetida $s_2$ como subsecuencia de $s_1$.

Entrada

Dos cadenas $s_1$ y $s_2$.

Salida

EL número de veces que $s_2$ aparece repetida como subsecuencia de $s_1$.

Observación

• Asuma que el tamaño máximo de $s_1$ es de $100$ caracteres;

• Una cadena $s_2$ es subsecuencia de otra $s_1$, si todos los caracteres de $s_2$ aparecen en el mismo orden en $s_1$, sin importar si aparecen de manera consecutiva o no. Por ejemplo la cadena $sa$ is subsecuencia de $espasa$ y aparece 2 veces, pero la cadena $se$ no es subsecuencia de $espasa$;

• No olvide imprimir un salto de línea al final.