Aguja en el Pajar

Enviar solució
Punts: 10 (parcial)
Temps Límit: 3.0s
Límit de memòria: 64M
Autor/a:
marc
tipus del problema
Combinatòria, Strings
Categoria
Extern
Llenguatges permesos
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

Comentaris


  • 0
    administrador  comentat a les set. 22, 2023, 5:52 p.m. ← editat

    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.