Interseção de deslocamentos cíclicos mínimos

C++ Hard strings

Tarefa «Interseção de deslocamentos cíclicos mínimos»

São dadas duas strings s e t, compostas por letras minúsculas latinas. É necessário encontrar o comprimento da maior substring comum que seja uma substring de algum deslocamento cíclico da string s e de algum deslocamento cíclico da string t. Deslocamento cíclico é uma permutação dos caracteres da string, onde todos os caracteres são deslocados k posições para a esquerda, e os caracteres que saem pela esquerda são transferidos para o final. O comprimento das strings não excede 10^5. Se nenhuma substring comum for encontrada, imprimir 0.

Formato de Entrada

Na primeira linha é dada a string s (1 ≤ |s| ≤ 10^5). Na segunda linha é dada a string t (1 ≤ |t| ≤ 10^5). As strings consistem apenas de letras minúsculas latinas.

Formato de Saída

Imprima um único número inteiro — o comprimento da maior substring comum que ocorre em algum deslocamento cíclico de s e em algum deslocamento cíclico de t.

Exemplos

Exemplo 1

ENTRADA

abc
def

SAÍDA

0

Exemplo 2

ENTRADA

bcd

SAÍDA

abc

main.cpp