Oppgave

Gitt $2$ strenger, skriv et program som finner den lengste strengen som er inneholdt i begge strengene, og oppgir lengden dens.

Her sies en streng $s$ å være inneholdt i en streng $t$ dersom $s$ forekommer sammenhengende i $t$. Den tomme strengen, altså strengen med lengde $0$, er inneholdt i enhver streng. For eksempel inneholder strengen ABRACADABRA følgende strenger: ABRA, RAC, D, ACADABRA, ABRACADABRA, den tomme strengen og så videre. På den annen side inneholder strengen ABRACADABRA ikke følgende strenger: ABRC, RAA, BA, K og så videre.

Forklarende eksempler

Eksempel $1$: Når ABRACADABRA og ECADADABRBCRDARA gis som strenger, omfatter strengene som er inneholdt i begge blant annet CA, CADA, ADABR og den tomme strengen. Den lengste av dem er ADABR, og lengden dens er $5$. Posisjonen til ADABR i de $2$ strengene er vist i Figur $2\text{-}1$.

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

Figur $2\text{-}1$: Posisjonen til ADABR i strengene i Eksempel $1$

Eksempel $2$: Når UPWJCIRUCAXIIRGL og SBQNYBSBZDFNEV gis som strenger, er den eneste strengen som er inneholdt i begge den tomme strengen, og lengden dens er $0$.

Inndata

Inndata består av $2$ linjer: på den $1$. linjen gis den $1$. strengen, og på den $2$. linjen gis den $2$. strengen. Strengene består av store engelske bokstaver, og lengden på hver streng er minst $1$ og høyst $4\,000$.

Av testdataene er lengden på hver streng minst $1$ og høyst $50$ for $30\%$ av poengene.

Utdata

Skriv ut $1$ linje som kun inneholder lengden på den lengste strengen som er inneholdt i begge de $2$ gitte strengene.

Eksempler på inndata og utdata

Inndata og utdata som tilsvarer eksemplene er som følger.

Eksempelinndata 1

ABRACADABRA
ECADADABRBCRDARA

Eksempelutdata 1

5

Eksempelinndata 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

Eksempelutdata 2

0