Aguja en el Pajar
Enviar solució
Bash, C Hashtag, C++, Haskell, Java, Kotlin, PHP, Python
Punts:
10 (parcial)
Temps Límit:
3.0s
Límit de memòria:
64M
Autor/a:
tipus del problema
Combinatòria, Strings
Categoria
Llenguatges permesos
Tienes una cadena N, llamada aguja, y una cadena H, llamada pajar, las cuales contienen solo letras minúsculas \(a..z\).
Escribe un programa para contar el número de permutaciones distintas de N que aparecen como una subcadena de H al menos una vez. Ten en cuenta que N puede tener entre 1 y \(N.length!\) permutaciones distintas en total; por ejemplo, la cadena aab tiene 3 permutaciones distintas (aab, aba y baa).
Entrada
La primera línea contiene la aguja, una string entre 1 y 200000 carácteres
La primera línea contiene el pajar, una string entre 1 y 200000 carácteres
Salida
El número de distintas permutaciones de N que hay en H
Ejemplo de Entrada 1
aab
abacabaaEjemplo de Salida 1
2
Comentaris
Si algú ho aconsegueix fer en Haskell que m'ho digui, jo em quedo sense memòria. (Puc evitar crear tot el conjunt de substrings en memòria, però aleshores l'operació de cerca és lineal i em quedo sense temps!)
Edit: Ho he acabat fent en C i ja està. Les restriccions de temps són una mica excessives potser.