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₁ y s₂ e imprima cuantas veces aparece repetida s₂ como subsecuencia de s₁.

Entrada

Dos cadenas s₁ y s₂.

Salida

EL número de veces que s₂ aparece repetida como subsecuencia de s₁.

Observación

• Asuma que el tamaño máximo de s₁ es de 100 caracteres;
• Una cadena s₂ es subsecuencia de otra s₁, si todos los caracteres de s₂ aparecen en el mismo orden en s₁, 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.