Intersection des décalages cycliques minimaux

C++ Hard strings

Tâche «Intersection des décalages cycliques minimaux»

Soient deux chaînes s et t composées de lettres minuscules latines. Il faut trouver la longueur de la plus grande sous-chaîne commune qui est une sous-chaîne d’un certain décalage cyclique de la chaîne s et d’un certain décalage cyclique de la chaîne t. Un décalage cyclique est une permutation des caractères d’une chaîne où tous les caractères sont décalés de k positions vers la gauche, et les caractères sortis à gauche sont déplacés à la fin. La longueur des chaînes ne dépasse pas 10^5. Si aucune sous-chaîne commune n’est trouvée, afficher 0.

Format d\ entrée

Sur la première ligne est donnée la chaîne s (1 ≤ |s| ≤ 10^5). Sur la deuxième ligne est donnée la chaîne t (1 ≤ |t| ≤ 10^5). Les chaînes sont composées uniquement de lettres minuscules latines.

Format de sortie

Affichez un seul entier — la longueur de la plus grande sous-chaîne commune qui apparaît dans un certain décalage cyclique de s et un certain décalage cyclique de t.

Exemples

Exemple 1

ENTRÉE

abc
def

SORTIE

0

Exemple 2

ENTRÉE

bcd

SORTIE

abc

main.cpp