Por Nacho Cabanes
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
hhhhhhhhoooooooolllllllaaaaaaaSalida
Caso #1: 0002
Caso #2: 0003
Caso #3: 0133
Caso #4: 1184
Caso #5: 3136