Reto al azar: 017

Actualmente tenemos 30 retos en nuestra base de datos. Accediendo al reto 17.

Nivel de dificultad aproximado (1 a 5): 3  

Recibirás una cadena de texto, y deberás decir cuántas veces aparece en ella la palabra "hola" como subsecuencia formada a partir de sus letras en orden.

Por ejemplo, si recibes la palabra "Hhoola" la respuesta sería 4, porque se podría tomar la primera H con la primera O (y con la L y con la A), la primera H con la segunda O, la segunda H con la primera O, o bien la segunda H con la segunda O. Si recibes "hobla", la respuesta sería 1. Si recibes "ohla", la respuesta sería 0, porque tras la H no hay ninguna O que permita completar la secuencia en orden.

Como el resultado puede ser un número muy grande, deberás mostrar sólo las 4 últimas cifras. Si es resultado tiene menos de 4 cifras, deberás completarlo con ceros por la izquierda hasta que sean exactamente 4 cifras.

Entrada

La primera línea de entrada contiene un único entero N, que es el número de casos de prueba. Las siguiente N líneas contienen los casos de prueba, uno por línea.

Salida

Para cada caso de prueba, la salida será

Caso #X: nnnn

donde X es el número de caso de prueba, a partir de 1, y nnnn son las cuatro últimas cifras de resultado (rellenas con ceros por la izquierda si es necesario).

Límites (en la propuesta original de Google Code Jam)

1 <= N <= 100

Conjunto de datos pequeño
longitud de cada línea <= 30

Conjunto de datos grande
longitud de cada línea <= 500

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)

Entrada
5
h olaa
hoho la
Hola, hola, hola, Que tal estas? Hola. Bienvenido a este lugar.
hhhhhoooollllaaaa es casi lo mismo que hola pero con las letras repetidas
hhhhhhhhoooooooolllllllaaaaaaa

Salida
Caso #1: 0002
Caso #2: 0003
Caso #3: 0133
Caso #4: 1184
Caso #5: 3136

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 2 más 3?
Lenguaje
Fuente: