Máxima Subcadena

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 256M

Authors:

ToOma_KFP, wizard98

Problem types

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Dada una cadena de caracteres $S$ ~S~, compuesta a lo mas por $10^5$ ~10^5~ letras mínusculas del alfabeto inglés. Su tarea es buscar una cadena $T$ ~T~ que tenga el mayor número de ocurrencias como subcadena en $S$ ~S~.

Si la solución no es única, se debe tomar la que tenga la máxima longitud. Si la solución sigue sin ser única, encuentre la más pequeña lexicográficamente.

Entrada

La primera línea de entrada contiene la cadena $S$ ~S~.

Salida

La primera línea de salida contiene la cadena $T$ ~T~.

Ejemplo de Entrada #1

cabdab

Ejemplo de Salida #1

ab

Ejemplo de Entrada #2

cabcabc

Ejemplo de Salida #2

Ejemplo de Entrada #3

ababababab

Ejemplo de Salida #3

ab

Explicación del ejemplo #1

$a$ ~a~, $b$ ~b~ y $ab$ ~ab~ aparecen $2$ ~2~ veces, pero $ab$ ~ab~ es más grande. No hay otras cadenas que aparezcan más de una vez.

Explicación del ejemplo #2

$c$ ~c~ aparece $3$ ~3~ veces mientras que $a$ ~a~, $b$ ~b~, $ab$ ~ab~, $ca$ ~ca~, $bc$ ~bc~, $abc$ ~abc~ y $cab$ ~cab~ aparecen solo $2$ ~2~ veces

Explicación del ejemplo #3

Ten en cuenta que estamos interesados en subcadenas(continuas), no subsecuencias.

$ab$ ~ab~ es el ganador con $5$ ~5~ apariciones.

Comments

-1

josue commented on March 8, 2023, 5:27 p.m.

Que modulo deberia usar en el hashing para este problema