Intersección de desplazamientos cíclicos mínimos

C++ Hard strings

Tarea «Intersección de desplazamientos cíclicos mínimos»

Se dan dos cadenas s y t, compuestas por letras latinas minúsculas. Es necesario encontrar la longitud de la subcadena común más larga que sea subcadena de algún desplazamiento cíclico de la cadena s y de algún desplazamiento cíclico de la cadena t. Un desplazamiento cíclico es una permutación de los caracteres de la cadena, donde todos los caracteres se desplazan k posiciones a la izquierda, y los caracteres que salen por la izquierda se trasladan al final. La longitud de las cadenas no supera 10^5. Si no se encuentra una subcadena común, se debe mostrar 0.

Formato de entrada

En la primera línea se da la cadena s (1 ≤ |s| ≤ 10^5). En la segunda línea se da la cadena t (1 ≤ |t| ≤ 10^5). Las cadenas consisten únicamente en letras latinas minúsculas.

Formato de salida

Muestre un único número entero: la longitud de la subcadena común más larga que aparece en algún desplazamiento cíclico de s y en algún desplazamiento cíclico de t.

Ejemplos

Ejemplo 1

ENTRADA

abc
def

SALIDA

0

Ejemplo 2

ENTRADA

bcd

SALIDA

abc

main.cpp