בעיה

בהינתן $2$ מחרוזות, כתבו תוכנית שתמצא את המחרוזת הארוכה ביותר המוכלת בשתי המחרוזות ותחזיר את אורכה.

כאן, אומרים שמחרוזת $s$ מוכלת במחרוזת $t$ אם $s$ מופיעה ברציפות בתוך $t$. המחרוזת הריקה, כלומר מחרוזת באורך $0$, מוכלת בכל מחרוזת. לדוגמה, המחרוזת ABRACADABRA מכילה את המחרוזות הבאות: ABRA, RAC, D, ACADABRA, ABRACADABRA, המחרוזת הריקה וכן הלאה. לעומת זאת, המחרוזת ABRACADABRA אינה מכילה את המחרוזות הבאות: ABRC, RAA, BA, K וכן הלאה.

דוגמאות להמחשה

דוגמה $1$: כאשר ניתנות המחרוזות ABRACADABRA ו-ECADADABRBCRDARA, בין המחרוזות המוכלות בשתיהן נמצאות CA, CADA, ADABR, המחרוזת הריקה וכן הלאה. הארוכה שבהן היא ADABR, ואורכה הוא $5$. המיקום של ADABR בתוך $2$ המחרוזות מוצג באיור $2\text{-}1$.

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

איור $2\text{-}1$: המיקום של ADABR המופיעה במחרוזות של דוגמה $1$

דוגמה $2$: כאשר ניתנות המחרוזות UPWJCIRUCAXIIRGL ו-SBQNYBSBZDFNEV, המחרוזת היחידה המוכלת בשתיהן היא המחרוזת הריקה, ואורכה הוא $0$.

קלט

הקלט מורכב מ-$2$ שורות: בשורה ה-$1$ ניתנת המחרוזת ה-$1$, ובשורה ה-$2$ ניתנת המחרוזת ה-$2$. המחרוזות מורכבות מאותיות אנגליות גדולות, ואורכה של כל מחרוזת הוא לפחות $1$ ולכל היותר $4\,000$.

מתוך נתוני הבדיקה, עבור $30\%$ מהניקוד אורכה של כל מחרוזת הוא לפחות $1$ ולכל היותר $50$.

פלט

הדפיסו שורה $1$ בלבד המכילה רק את אורכה של המחרוזת הארוכה ביותר המוכלת בשתי ($2$) המחרוזות הנתונות.

דוגמאות קלט ופלט

הקלט והפלט המתאימים לדוגמאות הם כדלקמן.

קלט לדוגמה 1

ABRACADABRA
ECADADABRBCRDARA

פלט לדוגמה 1

5

קלט לדוגמה 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

פלט לדוגמה 2

0