Problème

Étant donné $2$ chaînes de caractères, écrivez un programme permettant de trouver la plus longue chaîne contenue dans les deux chaînes et d'indiquer sa longueur.

Ici, on dit qu'une chaîne $s$ est contenue dans une chaîne $t$ si $s$ apparaît de manière contiguë dans $t$. La chaîne vide, c'est-à-dire la chaîne de longueur $0$, est contenue dans n'importe quelle chaîne. Par exemple, la chaîne ABRACADABRA contient les chaînes suivantes : ABRA, RAC, D, ACADABRA, ABRACADABRA, la chaîne vide, etc. En revanche, la chaîne ABRACADABRA ne contient pas les chaînes suivantes : ABRC, RAA, BA, K, etc.

Exemples explicatifs

Exemple $1$ : Lorsque les chaînes données sont ABRACADABRA et ECADADABRBCRDARA, les chaînes contenues dans les deux comprennent CA, CADA, ADABR, la chaîne vide, etc. Parmi celles-ci, la plus longue est ADABR, et sa longueur est $5$. Les positions de ADABR dans les $2$ chaînes sont indiquées sur la Figure $2\text{-}1$.

$$\begin{aligned} \texttt{ABRAC}&\underline{\texttt{ADABR}}\texttt{A} \\ \texttt{ECAD}&\underline{\texttt{ADABR}}\texttt{BCRDARA} \end{aligned}$$

Figure $2\text{-}1$ : Positions de ADABR apparaissant dans les chaînes de l'Exemple $1$

Exemple $2$ : Lorsque les chaînes données sont UPWJCIRUCAXIIRGL et SBQNYBSBZDFNEV, la seule chaîne contenue dans les deux est la chaîne vide, et sa longueur est $0$.

Entrée

L'entrée se compose de $2$ lignes : la $1$-ère chaîne est donnée sur la $1$-ère ligne et la $2$-ème chaîne est donnée sur la $2$-ème ligne. Les chaînes sont composées de lettres majuscules de l'alphabet anglais, et la longueur de chaque chaîne est comprise entre $1$ et $4\,000$ inclus.

Parmi les données d'évaluation, pour $30\%$ des points, la longueur de chaque chaîne est comprise entre $1$ et $50$ inclus.

Sortie

Affichez $1$ ligne contenant uniquement la longueur de la plus longue chaîne contenue à la fois dans les $2$ chaînes données.

Exemples d'entrée et de sortie

Les entrées et sorties correspondant aux exemples ci-dessus sont les suivantes.

Exemple d'entrée 1

ABRACADABRA
ECADADABRBCRDARA

Exemple de sortie 1

5

Exemple d'entrée 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

Exemple de sortie 2

0