Aguja en el Pajar
Submit solution
Bash, C#, C++, Haskell, Java, Kotlin, PHP, Python
Points:
10 (partial)
Time limit:
3.0s
Memory limit:
64M
Author:
Problem types
Combinatòria, Strings
Category
Allowed languages
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
abacabaa
Ejemplo de Salida 1
2
Comments
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.