Tehtävä

Kun annetaan $2$ merkkijonoa, kirjoita ohjelma, joka etsii pisimmän molempiin merkkijonoihin sisältyvän merkkijonon ja ilmoittaa sen pituuden.

Tässä merkkijonon $s$ sanotaan sisältyvän merkkijonoon $t$, jos $s$ esiintyy yhtäjaksoisesti $t$:ssä. Tyhjä merkkijono eli pituudeltaan $0$ oleva merkkijono sisältyy mihin tahansa merkkijonoon. Esimerkiksi merkkijonoon ABRACADABRA sisältyvät seuraavat merkkijonot: ABRA, RAC, D, ACADABRA, ABRACADABRA, tyhjä merkkijono ja niin edelleen. Toisaalta merkkijonoon ABRACADABRA eivät sisälly seuraavat merkkijonot: ABRC, RAA, BA, K ja niin edelleen.

Selittävät esimerkit

Esimerkki $1$: Kun merkkijonoiksi annetaan ABRACADABRA ja ECADADABRBCRDARA, molempiin sisältyviä merkkijonoja ovat muun muassa CA, CADA, ADABR ja tyhjä merkkijono. Näistä pisin on ADABR, ja sen pituus on $5$. Näihin $2$ merkkijonoon sisältyvän ADABR-osion sijainti on esitetty kuvassa $2\text{-}1$.

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

Kuva $2\text{-}1$: Esimerkin $1$ merkkijonoissa esiintyvän ADABR-osion sijainti

Esimerkki $2$: Kun merkkijonoiksi annetaan UPWJCIRUCAXIIRGL ja SBQNYBSBZDFNEV, ainoa molempiin sisältyvä merkkijono on tyhjä merkkijono, ja sen pituus on $0$.

Syöte

Syöte koostuu $2$ rivistä: $1$. rivillä annetaan $1$. merkkijono ja $2$. rivillä $2$. merkkijono. Merkkijonot koostuvat englannin kielen isoista kirjaimista, ja kummankin merkkijonon pituus on vähintään $1$ ja enintään $4\,000$.

Arvosteluaineistosta $30\%$ pisteistä on sellaisia, joissa kummankin merkkijonon pituus on vähintään $1$ ja enintään $50$.

Tuloste

Tulosta $1$ rivi, joka sisältää vain pisimmän molempiin annettuun $2$ merkkijonoon sisältyvän merkkijonon pituuden.

Esimerkkisyötteet ja -tulosteet

Esimerkkejä vastaavat syötteet ja tulosteet ovat seuraavat.

Esimerkkisyöte 1

ABRACADABRA
ECADADABRBCRDARA

Esimerkkituloste 1

5

Esimerkkisyöte 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

Esimerkkituloste 2

0