Encontrando Similitudes
Rafael es un niño de primaria y este curso aprendió a escribir. Sus profesores le han enseñado el alfabeto latino y lo han motivado a practicar la escritura de palabras a lápiz y papel. Como Rafael es muy pequeño las palabras que escribe generalmente no tienen mucho sentido y, curiosamente, siempre siguen la misma regla: empieza a escribir letras que conoce y cuando se aburre concatena al final una cantidad arbitraria de veces la palabra con la que se aburrió. O sea, si Rafael se aburre en la palabra "asa"podría dejar de escribir en las palabras "asaasa", "asaasaasa", y así sucesivamente.
Sucede que Rafael es un poco olvidadizo y a cada rato tiene que averiguar cuál fue la palabra que usó en las concatenaciones para obtener aquella que tiene escrita en el papel. Al ser tan joven e inexperto, se siente frustrado al no encontrarla pero él sabe que eres más que capaz de resolver su problema y, por eso, ruega tu ayuda. Te cuenta que cree que pueden haber varias palabras que cumplan sus requisitos, a pesar que él no encontró palabra alguna, por lo que te pide una lista con todas las palabras que puedan generar la escrita en el papel para así poder buscar la original con más facilidad.
Entrada
La primera línea de la entrada contiene un entero que representa la longitud de la palabra final
con la que termina Rafael en su hoja. La próxima y última línea es la palabra
, escrita usando letras minúsculas del alfabeto latino.
Salida
La salida cuenta con dos líneas. En la primera línea se espera un número que denota la cantidad de palabras que cumplen las restricciones de Rafael y en la segunda línea se requiere la lista de longitudes de las palabras seleccionadas estando los elementos de la lista ordenados de menor a mayor y separados por espacio.
Ejemplos
Entrada 1
6
asaasaSalida 1
1
3Entrada 2
20
aaaaaaaaaaaaaaaaaaaaSalida 2
5
1 2 4 5 10Restricción
para el 10% de los casos.
Comments
.
Que algoritmo c puede implementar aquí?
Obviamente, para que un string p se pueda concatenar varias veces él mismo obteniendo un string S, el tamaño de p debe ser divisor del tamaño de S. Entonces, si N es el tamaño del string de la entrada, iteramos por los prefijos cuyos tamaños sean divisores de N, y al estar en un prefijo de tamaño D, iteramos por los N/D segmentos de tamaño D del string y comprobamos si son iguales al prefijo de tamaño D (lo que se puede hacer con rolling Hashing); si todos son iguales, añadimos D a la solución.
Hola, tengo una duda, pueden mencionarme que algoritmo para búsqueda de patrones es más eficiente que el KMP??? este problema lo hice con tal método y me da Tiempo Límite Excedido en java.
Se incrementó el tiempo límite de Java y Python a 3 segs.