Aguja en el Pajar

Submit solution
Points: 10 (partial)
Time limit: 3.0s
Memory limit: 64M
Author:
marc
Problem types
Combinatòria, Strings
Category
Extern
Allowed languages
Bash, C#, C++, Haskell, Java, Kotlin, PHP, Python

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


  • 0
    administrador  commented on Sept. 22, 2023, 5:52 p.m. ← edited

    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.